¿Por qué si (n & -n) == n entonces n es una potencia de 2?

84

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?

David Weng
fuente
2
La nueva etiqueta debería ser una pista. :)
bzlm
10
Aquí está la respuesta: stackoverflow.com/questions/600293/…
Jacob Mattison
2
Siga los bits. Por cierto, también cuenta cero como potencia de dos. La fórmula (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).
harold
3
Sí, me declaro culpable de usar ese código. Hay una serie de trucos como este que puede jugar, siempre que sepa que está lidiando con la aritmética del complemento a 2 y sea consciente de las diversas dificultades de conversión y desbordamiento. Para obtener crédito adicional, averigüe cómo redondear a la siguiente potencia superior de dos, o quizás a la potencia de dos (1), cosas que deben hacerse con una frecuencia sorprendente en algunos trimestres.
Hot Licks
1
Espera, ¿ todos están leyendo de la fuente java.util.Random hoy en día? (Leí eso hace unos meses y recuerdo algunas preguntas al respecto en SO desde entonces.)
Mateen Ulhaq

Respuestas:

48

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...000

Para ver por qué esto funciona, considere el complemento a dos como inverso + 1, -n == ~n + 1

n          0000100...000
inverse n  1111011...111
                     + 1
two's comp 1111100...000

ya 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.

Mike Samuel
fuente
Y hay un truco para aislar el 1 bit menos significativo.
Hot Licks
2
En cuanto a (0 & -0) == 0, la declaración inmediatamente anterior es if (n <= 0) throw .... Lo que significa que el número bajo prueba nunca será 0 (o negativo) en ese momento.
usuario
1
@Michael, tiene razón. Estaba respondiendo la pregunta del título sin criticar lo Random.javaque no he leído.
Mike Samuel
1
@ Mike, me doy cuenta de eso; sin embargo, no creo que la declaración en el comentario en el código (que se incluye en la pregunta y es la base de la pregunta en el título) se mantenga por sí sola cuando no se ve en el contexto de los requisitos previos establecidos justo antes a él en el código. Si miras solo la pregunta tal como se publicó aquí, ni siquiera sabemos nada sobre qué tipo nes; No he comprobado esta suposición, pero de alguna manera dudo que a doublese comporte de la misma manera.
usuario
3
@Michael, podemos poner límites bastante buenos al tipo de nya que esta pregunta tiene la etiqueta "java". &no está definido en doubleo floaten Java. Solo se define en tipos enteros y booleanos. Dado -que no está definido para booleanos, podemos inferir con seguridad que nes integral.
Mike Samuel
95

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 que n & (that thing)sea ​​igual a n.

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.
Steve Jessop
fuente
13

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

Entonces, solo si ambos campos son 1, aparecerá un 1.

Ahora -n hace un complemento a 2. Cambia todo el 0a 1y se 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 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.

Johan
fuente
8

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      001000

Puede 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      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 se establecerá el menos significativo en el resultado.

Eclipse
fuente
4

Es propiedad de potencias de 2 y su complemento a dos .

Por ejemplo, tome 8:

8  = 0b00001000

-8 = 0b11111000

Calculando el complemento a dos:

Starting:  0b00001000
Flip bits: 0b11110111  (one's complement)
Add one:   0b11111000  

AND 8    : 0b00001000

Para 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.

Austin Salonen
fuente
4

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 de n(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 <<< n
Ing.Fouad
fuente
0

Mostrado a través del ejemplo:

8 en hexadecimal = 0x000008

-8 en hexadecimal = 0xFFFFF8

8 y -8 = 0x000008

Juan B
fuente