Multiplicar bitwise y agregar en Java

Tengo los métodos que hacen tanto la multiplicación como la sum, pero simplemente no puedo entenderlos. Ambos son de sitios web externos y no los míos:

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; // 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); } 

Intenté hacer una depuración paso a paso, pero realmente no tenía mucho sentido para mí, aunque funciona.

Lo que posiblemente estoy buscando es tratar de entender cómo funciona esto (¿la base matemática tal vez?).

Editar: Esto no es tarea, solo estoy tratando de aprender operaciones bit a bit en Java.

Comencemos mirando el código de multiplicación. La idea es bastante inteligente. Supongamos que tiene n 1 y n 2 escritos en binario. Entonces puedes pensar en n1 como una sum de potencias de dos: n2 = c 30 2 30 + c 29 2 29 + … + c 1 2 1 + c 0 2 0 , donde cada c i es 0 o 1. Entonces puede pensar en el producto n 1 n 2 como

n 1 n 2 =

n 1 (c 30 2 30 + c 29 2 29 + … + c 1 2 1 + c 0 2 0 ) =

n 1 c 30 2 30 + n 1 c 29 2 29 + … + n 1 c 1 2 1 + n 1 c 0 2 0

Esto es un poco denso, pero la idea es que el producto de los dos números viene dado por el primer número multiplicado por las potencias de dos que componen el segundo número, multiplicado por el valor de los dígitos binarios del segundo número.

La pregunta ahora es si podemos calcular los términos de esta sum sin hacer ninguna multiplicación real. Para hacerlo, vamos a necesitar poder leer los dígitos binarios de n 2 . Afortunadamente, podemos hacer esto utilizando turnos. En particular, supongamos que comenzamos con n 2 y luego solo miramos el último bit. Eso es c 0 . Si luego desplazamos el valor hacia abajo una posición, entonces el último bit es c 0 , etc. De manera más general, después de cambiar el valor de n 2 por i posiciones, el bit más bajo será c i . Para leer el último bit, podemos simplemente bitwise Y el valor con el número 1. Esto tiene una representación binaria que es cero en todas partes, excepto en el último dígito. Como 0 AND n = 0 para cualquier n, esto borra todos los bits superiores. Además, dado que 0 AND 1 = 0 y 1 AND 1 = 1, esta operación conserva el último bit del número.

De acuerdo, ahora sabemos que podemos leer los valores de c i ; ¿Y qué? Bueno, la buena noticia es que también podemos calcular los valores de la serie n 1 2 i de manera similar. En particular, considere la secuencia de valores n 1 << 0, n 1 << 1, etc. Cada vez que hace un cambio de bit izquierdo, es equivalente a multiplicar por una potencia de dos. Esto significa que ahora tenemos todos los componentes que necesitamos para calcular la suma anterior. Aquí está su código fuente original, comentado con lo que está pasando:

 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 esto ayude!

Parece que tu problema no es Java, sino solo calcular con números binarios. Inicio de simple: (todos los números binarios 🙂

 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 … Verás que puedes agregar dos números de un dígito usando la operación xor. Con un y ahora puede averiguar si tiene un bit de “acarreo”, que es muy similar a agregar números con lápiz y papel. (Hasta este punto tienes algo llamado Half-Adder). Cuando agrega los siguientes dos bits, también necesita agregar el bit de acarreo a esos dos dígitos. Teniendo esto en cuenta, puede obtener una Full-Adder. Puede leer sobre los conceptos de Half-Adders y Full-Adders en Wikipedia: http://en.wikipedia.org/wiki/Adder_(electronics ) Y muchos más lugares en la web. Espero que eso te sirva de inicio.

Con la multiplicación es muy similar por cierto. Solo recuerde cómo se multiplicó con lápiz y papel en la escuela primaria. Eso es lo que está pasando aquí. Solo que está sucediendo con números binarios y no con números decimales.

EXPLICACIÓN DEL MÉTODO bitwiseAdd:

Sé que esta pregunta fue hecha hace un tiempo, pero dado que no se ha dado una respuesta completa con respecto a cómo funciona el método bitwiseAdd aquí hay uno.

La clave para entender la lógica encapsulada en bitwiseAdd se encuentra en la relación entre las operaciones de adición y las operaciones xor y bitwise. Esa relación está definida por la siguiente ecuación (ver el apéndice 1 para un ejemplo numérico de esta ecuación):

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

O más simplemente:

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

Es posible que haya notado algo familiar en esta ecuación: las variables y y xor son las mismas que las definidas al principio de la adición de bits. También hay una multiplicación por dos, que en bitwiseAdd se realiza al principio del ciclo while. Pero volveré a eso más tarde.

Permítanme también hacer una nota lateral rápida sobre el operador ‘&’ bitwise antes de seguir adelante. Este operador básicamente “captura” la intersección de las secuencias de bits contra las cuales se aplica. Por ejemplo, 9 y 13 = 1001 y 1101 = 1001 (= 9). Puede ver en este resultado que solo los bits comunes a ambas secuencias de bits se copian en el resultado. De esto se deduce que cuando dos secuencias de bits no tienen un bit común, el resultado de aplicar ‘&’ sobre ellas produce 0 . Esto tiene una consecuencia importante en la relación bit a bit que se aclarará pronto

Ahora el problema que tenemos es que la ecuación 1.2 usa el operador ‘+’ mientras que bitwiseAdd no (solo usa ‘^’, ‘&’ y ‘<<'). Entonces, ¿cómo hacemos que el '+' en la ecuación 1.2 desaparezca de alguna manera? Respuesta: "forzando" a la expresión y a devolver 0. Y la forma en que lo hacemos es mediante el uso de la recursión .

Para demostrar esto voy a recurrir la ecuación 1.2 una vez (este paso puede ser un poco desafiante al principio, pero si es necesario, hay un resultado detallado paso a paso en el apéndice 2):

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

O más simplemente:

 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' 

Hay un par de cosas interesantes para notar aquí. Primero notó cómo el concepto de recursión suena parecido al de un bucle, como el que se encuentra en bitwiseAdd en realidad. Esta conexión se vuelve aún más obvia cuando se considera qué y [1] y xor [1] son: son las mismas expresiones que las expresiones y y xor definidas dentro del ciclo while en bitwiseAdd. También notamos que surge un patrón: ¡la ecuación 1.4 se ve exactamente como la ecuación 1.2!

Como resultado de esto, hacer más recursiones es muy fácil, si uno mantiene la notación recursiva. Aquí recurrimos la ecuación 1.2 dos veces más:

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

Esto debería ahora resaltar el rol de la variable ‘temp’ encontrada en bitwiseAdd: temp permite pasar de un nivel de recursión al siguiente.

También notamos la multiplicación por dos en todas esas ecuaciones. Como se mencionó anteriormente, esta multiplicación se realiza al comienzo del ciclo while en adición de bits usando la instrucción y << = 1 . Esta multiplicación tiene una consecuencia en la siguiente etapa de recursión ya que los bits en y [i] son ​​diferentes de los de en y [i] de la etapa anterior (y si recuerdas la pequeña nota lateral que hice antes sobre el operador ‘&’ probablemente ve a dónde va esto ahora).

La forma general de la ecuación 1.4 ahora se convierte en:

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

FINALY:

Entonces, ¿cuándo termina este negocio de recursión exactamente?

Respuesta: termina cuando la intersección entre las dos secuencias de bits en la expresión y [x] de la ecuación 1.5 devuelve 0 . El equivalente de esto en bitwiseAdd ocurre cuando la condición while loop se vuelve falsa. En este punto, la ecuación 1.5 se convierte en:

  x + y = xor[x] (1.6) 

Y eso explica por qué en bitwiseAdd solo devolvemos xor al final.

Y hemos terminado! Una pieza de código bastante inteligente, esta adición de bits. Debo decir 🙂

Espero que esto haya ayudado

APÉNDICE:

1) Un ejemplo numérico de la ecuación 1.1

la ecuación 1.1 dice:

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

Para verificar esta afirmación, uno puede tomar un ejemplo simple, por ejemplo, sumr 9 y 13 juntos. Los pasos se muestran a continuación (las representaciones en modo bit están entre paréntesis):

Tenemos

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

Y

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

volviendo a incluir eso en la ecuación 1.1 encontramos:

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

2) Demostrar el primer paso de recursión

La primera ecuación de recursión en la presentación (ecuación 1.3) dice que

Si

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

entonces

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

Para llegar a este resultado, simplemente tomamos la parte 2 * y + xor de la ecuación 1.2 anterior y aplicamos la relación adición / operandos bit a bit dada por la ecuación 1.1. Esto se demuestra de la siguiente manera:

Si

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

entonces

  [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) 

Simplificar esto con las definiciones de las variables y y xor de la ecuación 1.2 da el resultado de la ecuación 1.3:

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

Y usar esa misma simplificación da el resultado de la ecuación 1.4:

 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' 

Aquí hay otro enfoque para la multiplicación

 /** * 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); } 
    Intereting Posts