Bit a bit Multiplicar e Adicione em Java

https://stackoverflow.com/questions/4895173

28-10-2019
|

Pergunta

Eu tenho os métodos que fazem, ambos, a multiplicação e adição, mas simplesmente não sou capaz de colocar minha cabeça em torno deles.Ambos são de sites externos e não a minha:

public static void bitwiseMultiply(int n1, int n2) {
    int a = n1, b = n2, result=0;
    while (b != 0) // Iterate the loop till b==0
    {
        if ((b & 01) != 0) // Logical ANDing of the value of b with 01
        {
            result = result + a; // Update the result with the new value of a.
        }
        a <<= 1;              // Left shifting the value contained in 'a' by 1.
        b >>= 1;             // Right shifting the value contained in 'b' by 1.
    }
    System.out.println(result);
}

public static void bitwiseAdd(int n1, int n2) {
    int x = n1, y = n2;
    int xor, and, temp;
    and = x & y;
    xor = x ^ y;

    while (and != 0) {
        and <<= 1;
        temp = xor ^ and;
        and &= xor;
        xor = temp;
    }
    System.out.println(xor);
}

Eu tentei fazer um passo-a-passo de depuração, mas realmente não faz muito sentido para mim, embora ele funciona.

O que eu sou, possivelmente procurando é tentar entender como isso funciona (a base matemática, talvez?).

Editar:Isso não é lição de casa, eu só estou tentando aprender as operações bit a bit em Java.

Solução

Vamos começar examinando o código de multiplicação. A ideia é realmente muito inteligente. Suponha que você tenha n ₁ e n ₂ escrito em binário. Então você pode pensar em n1 como uma soma de potências de dois: n2= c ₃₀ 2 ³⁰ + c ₂₉ 2 ²⁹ + ... + c ₁ 2 ¹ + c ₀ 2 ⁰, onde cada c < sub> i é 0 ou 1. Então você pode pensar no produto n ₁ n ₂ como

n ₁ n ₂=

n ₁ (c ₃₀ 2 ³⁰ + c ₂₉ 2 ²⁹ + ... + c ₁ 2 ¹ + c ₀ 2 ⁰)=

n ₁ c ₃₀ 2 ³⁰ + n ₁ c ₂₉ 2 ²⁹ + ... + n ₁ c ₁ 2 ¹ + n ₁ c ₀ 2 ⁰

Isso é um pouco denso, mas a ideia é que o produto dos dois números seja dado pelo primeiro número multiplicado pelas potências de dois que formam o segundo número, vezes o valor dos dígitos binários do segundo número.

A questão agora é se podemos calcular os termos dessa soma sem fazer nenhuma multiplicação real. Para fazer isso, precisaremos ser capazes de ler os dígitos binários de n ₂. Felizmente, podemos fazer isso usando turnos. Em particular, suponha que comecemos com n ₂ e depois apenas olhemos para o último bit. Isso é c ₀. Se deslocarmos o valor uma posição para baixo, o último bit será c ₀, etc. Mais geralmente, depois de deslocar o valor de n ₂ para baixo em i posições, o o bit mais baixo será c _i. Para ler o último bit, podemos fazer o AND bit a bit do valor com o número 1. Isso tem uma representação binária que é zero em todo lugar, exceto no último dígito. Como 0 AND n= 0 para qualquer n, isso limpa todos os bits superiores. Além disso, como 0 AND 1= 0 e 1 AND 1= 1, esta operação preserva o último bit do número.

Ok - agora sabemos que podemos ler os valores de c _i; E daí? Bem, a boa notícia é que também podemos calcular os valores da série n ₁ 2 ⁱ de maneira semelhante. Em particular, considere a sequência de valores n ₁ << 0, n ₁ << 1, etc. Sempre que você fizer um deslocamento de bits para a esquerda, é equivalente a multiplicar por uma potência de dois. Isso significa que agora temos todos os componentes de que precisamos para calcular a soma acima. Aqui está seu código-fonte original, comentado com o que está acontecendo:

public static void bitwiseMultiply(int n1, int n2) {
    /* This value will hold n1 * 2^i for varying values of i.  It will
     * start off holding n1 * 2^0 = n1, and after each iteration will 
     * be updated to hold the next term in the sequence.
     */
    int a = n1;

    /* This value will be used to read the individual bits out of n2.
     * We'll use the shifting trick to read the bits and will maintain
     * the invariant that after i iterations, b is equal to n2 >> i.
     */
    int b = n2;

    /* This value will hold the sum of the terms so far. */
    int result = 0;

    /* Continuously loop over more and more bits of n2 until we've
     * consumed the last of them.  Since after i iterations of the
     * loop b = n2 >> i, this only reaches zero once we've used up
     * all the bits of the original value of n2.
     */
    while (b != 0)
    {
        /* Using the bitwise AND trick, determine whether the ith 
         * bit of b is a zero or one.  If it's a zero, then the
         * current term in our sum is zero and we don't do anything.
         * Otherwise, then we should add n1 * 2^i.
         */
        if ((b & 1) != 0)
        {
            /* Recall that a = n1 * 2^i at this point, so we're adding
             * in the next term in the sum.
             */
            result = result + a;
        }

        /* To maintain that a = n1 * 2^i after i iterations, scale it
         * by a factor of two by left shifting one position.
         */
        a <<= 1;

        /* To maintain that b = n2 >> i after i iterations, shift it
         * one spot over.
         */
        b >>>= 1;
    }

    System.out.println(result);
}

Espero que isso ajude!

Outras dicas

Parece que seu problema não é java, mas apenas cálculos com números binários. Começo do simples: (todos os números binários :)

0 + 0 = 0   # 0 xor 0 = 0
0 + 1 = 1   # 0 xor 1 = 1
1 + 0 = 1   # 1 xor 0 = 1
1 + 1 = 10  # 1 xor 1 = 0 ( read 1 + 1 = 10 as 1 + 1 = 0 and 1 carry)

Ok ... Você verá que pode adicionar dois números de um dígito usando a operação xor. Com um e agora você pode descobrir se tem um bit de "transporte", que é muito semelhante a adicionar números com caneta e papel. (Até este ponto você tem algo chamado Meio-Víbora). Quando você adiciona os próximos dois bits, também precisa adicionar o bit de transporte a esses dois dígitos. Levando isso em consideração, você pode obter um Full-Adder. Você pode ler sobre os conceitos de Metade-Adicionadores e Adicionadores Completos na Wikipedia: http://en.wikipedia.org/wiki/Adder_(electronics ) E muitos mais lugares na web. Espero que você comece.

Com a multiplicação, é muito parecido. Lembre-se de como você fez a multiplicação com papel e caneta na escola primária. Isso é o que está acontecendo aqui. Só que está acontecendo com números binários e não com números decimais.

EXPLICAÇÃO DO bitwiseAdd MÉTODO:

Eu sei que esta pergunta foi feita a um tempo atrás, mas já que nenhuma resposta completa foi dada a respeito de como o bitwiseAdd método funciona aqui é um.

A chave para entender a lógica encapsulado em bitwiseAdd é encontrado na relação entre além de operações e xor e e operações bit a bit.Que relação é definida pela seguinte equação (ver anexo 1 para um exemplo numérico da equação):

x + y = 2 * (x&y)+(x^y)     (1.1)

Ou, mais simplesmente:

x + y = 2 * and + xor       (1.2)

with
    and = x & y
    xor = x ^ y

Você pode ter notado algo de familiar nesta equação:o e e xor as variáveis são as mesmas definidas no início do bitwiseAdd.Há também uma multiplicação por dois, o que na bitwiseAdd é feito no início do loop while.Mas eu vou voltar a isso mais tarde.

Deixe-me também fazer uma rápida nota sobre o '&' operador bit a bit antes de prosseguir. Este operador, basicamente, "captura" o ponto de intersecção das sequências de bits, contra a qual ela é aplicada.Por exemplo, 9 & 13 = 1001 & 1101 = 1001 (=9).Você pode ver a partir deste resultado que somente os bits comuns a ambas as sequências de bits são copiados para o resultado.Ele deriva que, quando duas sequências de bits de bits, o resultado da aplicação '&' sobre eles rendimentos 0. Isso tem uma consequência importante no além-bit a bit relação que deve ficar claro logo

Agora, o problema que temos é que a equação 1.2 usa o operador " + " considerando que bitwiseAdd não (ele só usa '^', '&' e '<<').Então, como fazemos o '+' na equação 1.2, de alguma forma desaparecer?Resposta:por 'forçar' o e expressão para retornar 0.E a forma de fazer isto é usando a recursão.

Para demonstrar isso, eu estou indo para recurse equação 1.2 uma vez (esta etapa pode ser um pouco difícil no começo, mas, se necessário, há um detalhado passo a passo resultado no apêndice 2):

x + y = 2*(2*and & xor) + (2*and ^ xor)     (1.3)

Ou, mais simplesmente:

x + y = 2 * and[1] + xor[1]     (1.4)

with
    and[1] = 2*and & xor,
    xor[1] = 2*and ^ xor,
    [1] meaning 'recursed one time'

Há um par de coisas interessantes para observação aqui.Primeiro você notou como o conceito de recursividade sons próximo ao de um loop, como o encontrado em bitwiseAdd na verdade.Esta ligação torna-se ainda mais evidente quando se considera que e[1] e xor[1] são:eles são o mesmo expressões como a e e xor expressões definidas DENTRO o loop while em bitwiseAdd.Observamos também que um padrão emerge:equação 1.4 se parece exatamente como a equação 1.2!

Como resultado desta, fazendo mais recursions é uma brisa, se mantiver o recursiva de notação.Aqui nós recurse equação 1.2 mais duas vezes:

x + y = 2 * and[2] + xor[2]
x + y = 2 * and[3] + xor[3]

Este deve agora destacar o papel do 'temp' variável encontrada em bitwiseAdd: temp permite passar de um nível de recursão para o próximo.

Também vemos a multiplicação por dois, em todas as equações.Como mencionado anteriormente, essa multiplicação é feita no início do loop while em bitwiseAdd usando o e <<= 1 instrução.Esta multiplicação tem uma consequência no próximo recursão fase uma vez que os bits e[i] são diferentes dos da e[i] do estágio anterior (e se você se lembrar do pouco de lado a observação que fiz anteriormente sobre o operador '&' você provavelmente onde isto está indo agora).

A forma geral da equação 1.4, agora, torna-se:

x + y = 2 * and[x] + xor[x]     (1.5)
with x the nth recursion

FINALMENTE:

Assim, quando faz isso de recursão ponta do negócio, exatamente?

Resposta: ela termina quando a intersecção entre as duas sequências de bits no e[x] expressão da equação 1.5 retorna 0.O equivalente a isto em bitwiseAdd acontece quando o loop enquanto a condição se torna falsa.Neste ponto equação 1.5 torna-se:

    x + y = xor[x]      (1.6)

E o que explica por que, em bitwiseAdd nós só retorno xor no final!

E nós somos feitos!Bastante inteligente pedaço de código que esta bitwiseAdd devo dizer :)

Espero que isto tenha ajudado

APÊNDICE:

1) Um exemplo numérico da equação 1.1

equação 1.1 diz:

    x + y = 2(x&y)+(x^y)        (1.1)

Para verificar esta afirmação pode-se tomar um exemplo simples, digamos que a adição de 9 e 13 juntos.Os passos são apresentados a seguir (bit-a-bit representações estão entre parênteses):

Nós temos

    x = 9 (1001)
    y = 13  (1101)

    x + y = 9 + 13 = 22
    x & y = 9 & 13 = 9 (1001 & 1101 = 1001)
    x ^ y = 9^13 = 4 (1001 ^ 1101 = 0100)

pluging que volta na equação 1.1, podemos encontrar:

    9 + 13 = 2 * 9 + 4 = 22 et voila!

2) Demonstrando o primeiro passo de recursão

O primeiro recursão equação na apresentação (equação 1.3) diz que

x + y = 2 * and + xor           (equation 1.2)

em seguida,

x + y = 2*(2*and & xor) + (2*and ^ xor)     (equation 1.3)

Para chegar a este resultado, nós simplesmente tomou o 2* e + xor parte da equação 1.2, acima, e aplicada a adição/bit a bit operandos relação dada pela equação 1.1 a ele.Isso é demonstrado como segue:

    x + y = 2(x&y) + (x^y)      (equation 1.1)

em seguida,

     [2(x&y)] + (x^y)     =      2 ([2(x&y)] & (x^y)) + ([2(x&y)] ^ (x^y))
(left side of equation 1.1)  (after applying the addition/bitwise operands relationship)

Simplificando esta com as definições da e e xor variáveis da equação 1.2 dá equação 1.3 o resultado:

[2(x&y)] + (x^y) = 2*(2*and & xor) + (2*and ^ xor)

with
    and = x&y
    xor = x^y

E usando a mesma simplificação dá equação 1.4 resultado:

2*(2*and & xor) + (2*and ^ xor) = 2*and[1] + xor[1]

with
    and[1] = 2*and & xor
    xor[1] = 2*and ^ xor
    [1] meaning 'recursed one time'

Aqui está outra abordagem para multiplicação

/**
 * Multiplication of binary numbers without using '*' operator
 * uses bitwise Shifting/Anding
 *
 * @param n1
 * @param n2
 */
public static void multiply(int n1, int n2) {
    int temp, i = 0, result = 0;

    while (n2 != 0) {
        if ((n2 & 1) == 1) {
            temp = n1;

            // result += (temp>>=(1/i)); // To do it only using Right shift
            result += (temp<<=i); // Left shift (temp * 2^i)
        }
        n2 >>= 1;   // Right shift n2 by 1.
        i++;
    }

    System.out.println(result);
}

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow