Bitshifting en Java

Question

Estoy tratando de entender cómo funciona el cambio de bits. Por favor alguien puede explicar el significado de esta línea:

while ((n&1)==0) n >>= 1; 

donde n es un entero y me dan un ejemplo de un n cuando se ejecuta el cambio.

Answer 1

Supongamos n = 12. Los bits para esto serían 1100 (1 * 8 + 1 * 4 + 0 * 2 + 0 * 1 = 12). La primera vez en el bucle n & 1 == 0 porque el último dígito de 1100 es 0 y cuando AND es 1, obtiene 0. Entonces n >> = 1 hará que n cambie de 1100 (12) a 110 (6). Como puede observar, desplazar hacia la derecha tiene el mismo efecto que dividir por 2. El último bit sigue siendo cero, por lo que n & 1 seguirá siendo 0, por lo que cambiará a la derecha una vez más. n >> = 1 hará que cambie un dígito más a la derecha cambiando n de 110 (6) a 11 (3).

Ahora puede ver que el último bit es 1, por lo que n & 1 será 1, haciendo que el ciclo while deje de ejecutarse. El propósito del ciclo parece ser desplazar el número hacia la derecha hasta que encuentre el primer bit encendido (hasta que el resultado sea impar).

Answer 2

n & 1 es en realidad una operación Y a nivel de bit. Aquí, el patrón de bits de n se ANDARía contra el patrón de bits de 1. ¿Quién será el resultado comparado con cero? En caso afirmativo, n es el derecho desplazado 1 vez. Puede tomar el cambio a la derecha como división por 2 y así sucesivamente.

Answer 3

Descomponiéndola:

n & 1 va a hacer una comparación binaria entre N y 1, que es 00000000000000000000000000000001 en binario. Como tal, devolverá 00000000000000000000000000000001 cuando n finalice en un 1 (número par positivo impar o negativo) y 00000000000000000000000000000000 en caso contrario.

(n & 1) == 0 será, por lo tanto, verdadero si n es par (o impar negativo) y falso de lo contrario.

n >> = 1 es equivalente a n = n >> 1. Como tal, desplaza todos los bits a la derecha, que es más o menos equivalente a una división por dos (redondeo hacia abajo).

Si, por ejemplo, n comenzó como 12 y luego en binario sería 1100. Después de un bucle será 110 (6), después de otro será 11 (3) y luego el bucle se detendrá.

Si n es 0, entonces después del siguiente ciclo seguirá siendo 0, y el ciclo será infinito.

Answer 4

por ejemplo, si n era

n= b11110000 

entonces

n&1= b11110000 & 
     b00000001 
     --------- 
     b00000000 

n>>=1 b11110000 >> 1 
     --------- 
     b01111000 

n= b01111000 

si el bucle continúa debería ser

n= b00001111 

Answer 5

Lets n ser 4 que en binario se representa como:

00000000 00000000 00000000 00000100 

(n&1) en bits y el n con 1.
1 tiene la representación binaria de:

00000000 00000000 00000000 00000001 

El resultado de la operación AND bit a bit es 0:

00000000 00000000 00000000 00000100 = n 
00000000 00000000 00000000 00000001 = 1 
------------------------------------ 
00000000 00000000 00000000 00000000 = 0 

lo que la condición de tiempo es cierto.
Efectivamente, se usó (n&1) para extraer el bit menos significativo del n.

En el bucle while se gira a la derecha (>>) n por 1. Desplazar a la derecha un número por k es lo mismo que dividir el número por 2^k.

n que ahora 00000000 00000000 00000000 00000100 está a la derecha cambiando una vez que se convierte en 00000000 00000000 00000000 00000010 que es 2.

A continuación se extrae el LSB (bit menos significativo) de n nuevo que es 0 y desplazamiento a la derecha de nuevo para dar 00000000 00000000 00000000 0000001 que es 1.

A continuación volvemos a extraer LSB de n, que ahora es 1 y el bucle se rompe.

Así eficacia con la que se siguen dividiendo su número de n por 2 hasta que se convierte impares números impares tienen su conjunto LSB.

También tenga en cuenta que si es n0 Para empezar se va a ir en un bucle infinito porque no importa cuántas veces se divide 0 por 2 no se obtendrá un número impar.

Answer 6

Vamos a suponer que es igual 42 (sólo porque):

int n = 42; 

while ((n & 1) == 0) { 
    n >>= 1; 
} 

iteración 0:

• n = 42 (o 0000 0000 0000 0000 0000 0000 0010 1010)
• n & 1 == 0 es true (porque n & 1 = 0 o 0000 0000 0000 0000 0000 0000 0000 0000)

iteración 1:

• n = 21 (o 0000 0000 0000 0000 0000 0000 0001 0101)
• n & 1 == 0 es false (porque n & 1 == 1 o 0000 0000 0000 0000 0000 0000 0000 0001)

Lo que hace:

Básicamente, se bucle divide n por 2, siempre y cuando n es un número par:

• n & 1 es un simple comprobación de paridad,
• n >> = 1 desplaza los bits a la derecha, que simplemente se divide por 2.