La línea 294 de la fuente java.util.Random dice
if ((n & -n) == n) // i.e., n is a power of 2
// rest of the code
¿Por qué es esto?
java
logic
bit-manipulation
David Weng
fuente
fuente
(n & (n - 1)) == 0también funciona (elimina el bit de orden más bajo, si no quedan bits, entonces había como máximo 1 bit establecido en primer lugar).Respuestas:
La descripción no es del todo precisa porque
(0 & -0) == 00 no es una potencia de dos. Una mejor forma de decirlo es((n & -n) == n)cuando n es una potencia de dos, o el negativo de una potencia de dos, o cero.Si n es una potencia de dos, entonces n en binario es un solo 1 seguido de ceros. -n en complemento a dos es el inverso + 1 por lo que los bits se alinean así
n 0000100...000 -n 1111100...000 n & -n 0000100...000Para ver por qué esto funciona, considere el complemento a dos como inverso + 1,
-n == ~n + 1n 0000100...000 inverse n 1111011...111 + 1 two's comp 1111100...000ya que lleva el uno hasta el final al agregar uno para obtener el complemento de dos.
Si n fuera diferente a una potencia de dos †, entonces el resultado faltaría un poco porque el complemento a dos no tendría el bit más alto establecido debido a ese acarreo.
† - o cero o un negativo de una potencia de dos ... como se explica en la parte superior.
fuente
(0 & -0) == 0, la declaración inmediatamente anterior esif (n <= 0) throw .... Lo que significa que el número bajo prueba nunca será 0 (o negativo) en ese momento.Random.javaque no he leído.nes; No he comprobado esta suposición, pero de alguna manera dudo que adoublese comporte de la misma manera.nya que esta pregunta tiene la etiqueta "java".&no está definido endoubleofloaten Java. Solo se define en tipos enteros y booleanos. Dado-que no está definido para booleanos, podemos inferir con seguridad quenes integral.Porque en complemento a 2,
-nes~n+1.Si
nes una potencia de 2, entonces solo tiene un bit establecido. Así que~ntiene todos los bits establecidos excepto ese. Agregue 1 y vuelva a establecer el bit especial, asegurándose de quen & (that thing)sea igual an.Lo contrario también es cierto porque el 0 y los números negativos fueron descartados por la línea anterior en esa fuente de Java. Si
ntiene más de un bit establecido, entonces uno de ellos es el bit más alto. Este bit no será establecido por el+1porque hay un bit claro más bajo para "absorberlo":n: 00001001000 ~n: 11110110111 -n: 11110111000 // the first 0 bit "absorbed" the +1 ^ | (n & -n) fails to equal n at this bit.fuente
Necesita mirar los valores como mapas de bits para ver por qué esto es cierto:
1 & 1 = 1 1 & 0 = 0 0 & 1 = 0 0 & 0 = 0Entonces, solo si ambos campos son 1, aparecerá un 1.
Ahora -n hace un complemento a 2. Cambia todo el
0a1y se añade 1.7 = 00000111 -1 = NEG(7) + 1 = 11111000 + 1 = 11111001sin embargo
8 = 00001000 -8 = 11110111 + 1 = 11111000 00001000 (8) 11111000 (-8) --------- & 00001000 = 8.Solo para potencias de 2 será
(n & -n)n.Esto se debe a que una potencia de 2 se representa como un conjunto de bits único en un largo mar de ceros. La negación producirá exactamente lo contrario, un solo cero (en el lugar donde solía estar el 1) en un mar de unos. Agregar 1 desplazará los inferiores al espacio donde está el cero.
Y el bit a bit y (&) filtrarán el 1 nuevamente.
fuente
En la representación del complemento a dos, lo único de las potencias de dos es que constan de todos los bits 0, excepto el bit kth, donde n = 2 ^ k:
base 2 base 10 000001 = 1 000010 = 2 000100 = 4 ...Para obtener un valor negativo en complemento a dos, invierte todos los bits y agrega uno. Para potencias de dos, eso significa que obtienes un montón de 1 a la izquierda hasta el 1 bit que estaba en el valor positivo, y luego un montón de 0 a la derecha:
n base 2 ~n ~n+1 (-n) n&-n 1 000001 111110 111111 000001 2 000010 111101 111110 000010 4 000100 111011 111100 000100 8 001000 110111 111000 001000Puede ver fácilmente que el resultado de las columnas 2 y 4 será el mismo que el de la columna 2.
Si observa los otros valores que faltan en este gráfico, puede ver por qué esto no es válido para nada más que los poderes de dos:
n base 2 ~n ~n+1 (-n) n&-n 1 000001 111110 111111 000001 2 000010 111101 111110 000010 3 000011 111100 111101 000001 4 000100 111011 111100 000100 5 000101 111010 111011 000001 6 000110 111001 111010 000010 7 000111 111000 111001 000001 8 001000 110111 111000 001000n & -n (para n> 0) solo tendrá 1 bit establecido, y ese bit será el bit establecido menos significativo en n. Para todos los números que son potencias de dos, el bit establecido menos significativo es el único bit establecido. Para todos los demás números, hay más de un conjunto de bits, de los cuales solo se establecerá el menos significativo en el resultado.
fuente
Es propiedad de potencias de 2 y su complemento a dos .
Por ejemplo, tome 8:
8 = 0b00001000 -8 = 0b11111000Calculando el complemento a dos:
Starting: 0b00001000 Flip bits: 0b11110111 (one's complement) Add one: 0b11111000 AND 8 : 0b00001000Para potencias de 2, sólo un bit se establecerá así que la adición hará que el n ésimo bit de 2 n a ser establecido (el que mantiene llevando a la n º bit). Luego, cuando tienes
ANDlos dos números, recuperas el original.Para los números que no son potencias de 2, los otros bits no se invertirán, por lo
ANDque no producirán el número original.fuente
Simplemente, si n es una potencia de 2, eso significa que solo un bit se establece en 1 y los otros son 0:
00000...00001 = 2 ^ 0 00000...00010 = 2 ^ 1 00000...00100 = 2 ^ 2 00000...01000 = 2 ^ 3 00000...10000 = 2 ^ 4 and so on ...y porque
-nes un complemento a 2 den(eso significa que el único bit que es 1 permanece como está y los bits en el lado izquierdo de ese bit se sitúan en 1, lo que en realidad no importa, ya que el resultado del operador AND&será 0 si uno de los dos bits es cero):000000...000010000...00000 <<< n & 111111...111110000...00000 <<< -n -------------------------- 000000...000010000...00000 <<< nfuente
Mostrado a través del ejemplo:
8 en hexadecimal = 0x000008
-8 en hexadecimal = 0xFFFFF8
8 y -8 = 0x000008
fuente