Por qué si (n & n) == n, entonces n es una potencia de 2?
Línea 294 de Java.útil.Fuente aleatoria dice:
if ((n & -n) == n) // i.e., n is a power of 2
// rest of the code
¿Por qué es esto?
7 answers
La descripción no es del todo precisa porque (0 & -0) == 0 pero 0 no es una potencia de dos. Una mejor manera 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 el complemento de dos es el inverso + 1 por lo que los bits se alinean así
n 0000100...000
-n 1111100...000
n & -n 0000100...000
Para ver por qué este trabajo, considere el complemento de dos como inverso + 1, -n == ~n + 1
n 0000100...000
inverse n 1111011...111
+ 1
two's comp 1111100...000
Ya que llevas el uno todos los camino a través de la adición de uno para obtener el complemento de los dos.
Si n fuera otra cosa que una potencia de dos†, entonces el resultado faltaría un poco porque el complemento de los dos no tendría el bit más alto establecido debido a que lleva.
† - o cero o un negativo de una potencia de dos ... como se explica en la parte superior.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-08-20 16:43:41
Porque en el complemento de 2, -n es ~n+1.
Si n es una potencia de 2, entonces solo tiene un bit establecido. Así que ~n tiene todos los bits establecidos excepto ese. Añade 1 y vuelve a configurar el bit especial, asegurándote de que n & (that thing) es igual a n.
Lo contrario también es cierto porque los números 0 y negativos fueron descartados por la línea anterior en esa fuente Java. Si n tiene más de un bit establecido, entonces uno de ellos es el bit más alto. Este bit no será establecido por el +1 porque hay un bit claro inferior para" absorberlo":
n: 00001001000
~n: 11110110111
-n: 11110111000 // the first 0 bit "absorbed" the +1
^
|
(n & -n) fails to equal n at this bit.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-09-27 11:13:21
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 = 0
Así que solo si ambos campos son 1 saldrá un 1.
Ahora-n hace un complemento de 2. Cambia todo el 0 a 1 y añade 1.
7 = 00000111
-1 = NEG(7) + 1 = 11111000 + 1 = 11111001
Sin 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 solo bit de conjunto en un largo mar de cero.
La negación producirá exactamente lo contrario, un único cero (en el punto donde el 1 solía ser) en un mar de 1. Agregando 1 desplazará los más bajos al espacio donde está el cero.
Y El bitwise y (&) filtrará el 1 de nuevo.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-09-13 16:53:22
En la representación del complemento de dos, lo único de las potencias de dos, es que consisten en 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 el complemento de two, voltea todos los bits y agrega uno. Para potencias de dos, eso significa que obtienes un montón de 1s a la izquierda hasta e incluyendo el bit 1 que estaba en el valor positivo, y luego un montón de 0s 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 001000
Puede ver fácilmente que el resultado de la columna 2 y 4 va a sea lo mismo que la columna 2.
Si nos fijamos en los otros valores que faltan en este gráfico, se puede ver por qué esto no se sostiene 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 001000
N&-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 el menos significativo se establecerá en el resultado.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-09-13 20:09:36
Es propiedad de los poderes de 2 y su complemento de dos.
Por ejemplo, toma 8:
8 = 0b00001000
-8 = 0b11111000
Calculando el complemento de los dos:
Starting: 0b00001000
Flip bits: 0b11110111 (one's complement)
Add one: 0b11111000
AND 8 : 0b00001000
Para potencias de 2, solo se establecerá un bit por lo que agregar causará que se establezca el bit nth de 2n (el que sigue llevando al bit nth). Luego, cuando AND los dos números, se obtiene el original de vuelta.
Para números que no son potencias de 2, otros bits no obtendrán volteado para que el AND no produzca el número original.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-09-13 17:00:09
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 -n es un complemento de 2 de n (eso significa que el único bit que es 1 permanece como está y los bits en el lado izquierdo de ese bit son sit a 1 que en realidad no importa ya que el resultado de Y operador & será 0 si uno de los dos bits es cero):
000000...000010000...00000 <<< n
&
111111...111110000...00000 <<< -n
--------------------------
000000...000010000...00000 <<< n
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-09-13 17:20:41
Se muestra a través del ejemplo:
8 en hex = 0x000008
-8 en hex = 0xFFFFF8
8 & -8 = 0x000008
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-09-13 16:51:46