Pourquoi si (n & -n) == n alors n est une puissance de 2?

La ligne 294 de la source java.util.Random indique

if ((n & -n) == n) // i.e., n is a power of 2
    // rest of the code

Pourquoi est-ce?

La description n'est pas tout à fait exacte car (0 & -0) == 0mais 0 n'est pas une puissance de deux. Une meilleure façon de dire que c'est

((n & -n) == n) quand n est une puissance de deux, ou le négatif d'une puissance de deux, ou zéro.

Si n est une puissance de deux, alors n en binaire est un simple 1 suivi de zéros. -n en complément à deux est l'inverse + 1 donc les bits s'alignent ainsi

 n      0000100...000
-n      1111100...000
 n & -n 0000100...000

Pour voir pourquoi ce travail, considérez le complément à deux comme inverse + 1, -n == ~n + 1

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

puisque vous portez celui tout au long de l'ajout d'un pour obtenir le complément à deux.

Si n était autre chose qu'une puissance de deux †, alors le résultat manquerait un peu parce que le complément à deux n'aurait pas le bit le plus élevé en raison de cette retenue.

† - ou zéro ou un négatif d'une puissance de deux ... comme expliqué en haut.

Parce que dans le complément de 2, -nest ~n+1.

Si nest une puissance de 2, alors il n'a qu'un seul bit défini. Donc, ~ntous les bits sont définis sauf celui-là. Ajoutez 1 et vous définissez à nouveau le bit spécial, en vous assurant qu'il n & (that thing)est égal à n.

L'inverse est également vrai car les nombres 0 et négatifs ont été exclus par la ligne précédente dans cette source Java. Si nplus d'un bit est défini, l'un de ces bits est le bit le plus élevé. Ce bit ne sera pas défini par le+1 car il existe un bit clair inférieur pour "l'absorber":

 n: 00001001000
~n: 11110110111
-n: 11110111000  // the first 0 bit "absorbed" the +1
        ^
        |
        (n & -n) fails to equal n at this bit.

Vous devez regarder les valeurs sous forme de bitmaps pour voir pourquoi cela est vrai:

1 & 1 = 1
1 & 0 = 0
0 & 1 = 0
0 & 0 = 0

Donc, ce n'est que si les deux champs sont 1 qu'un 1 sortira.

Maintenant -n fait un complément à 2. Il change tout le 0en 1et il ajoute 1.

7 = 00000111
-1 = NEG(7) + 1 = 11111000 + 1 = 11111001

pourtant

8 = 00001000
-8 = 11110111 + 1 = 11111000 

00001000  (8)
11111000  (-8)
--------- &
00001000 = 8.

Seulement pour les puissances de 2 sera (n & -n)n.
En effet, une puissance de 2 est représentée comme un seul bit défini dans une longue mer de zéro. La négation donnera l'exact opposé, un seul zéro (à l'endroit où se trouvait le 1) dans une mer de 1. Ajouter 1 déplacera les inférieurs dans l'espace où se trouve le zéro.
Et les bits et (&) filtreront à nouveau le 1.

Dans la représentation du complément à deux, la particularité des puissances de deux est qu'elles se composent des 0 bits, à l'exception du kème bit, où n = 2 ^ k:

base 2    base 10
000001 =  1 
000010 =  2
000100 =  4
     ...

Pour obtenir une valeur négative dans le complément à deux, vous retournez tous les bits et en ajoutez un. Pour les puissances de deux, cela signifie que vous obtenez un groupe de 1 sur la gauche jusqu'à et y compris le 1 bit qui était dans la valeur positive, puis un groupe de 0 sur la droite:

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

Vous pouvez facilement voir que le résultat des colonnes 2 et 4 sera le même que celui de la colonne 2.

Si vous regardez les autres valeurs absentes de ce graphique, vous pouvez voir pourquoi cela ne vaut rien d'autre que les puissances de deux:

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 n'aura (pour n> 0) que 1 bit défini, et ce bit sera le bit défini le moins significatif dans n. Pour tous les nombres qui sont des puissances de deux, le bit défini le moins significatif est le seul bit défini. Pour tous les autres nombres, il y a plus d'un bit défini, dont seul le moins significatif sera défini dans le résultat.

C'est la propriété des puissances de 2 et du complément de leurs deux .

Par exemple, prenez 8:

8  = 0b00001000

-8 = 0b11111000

Calcul du complément à deux:

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

AND 8    : 0b00001000

Pour les puissances de 2, un seul bit sera mis à 1, donc l'ajout entraînera la mise à 1 du n ^ème bit de 2 ⁿ (celui qui continue de porter au n ^ème bit). Ensuite, lorsque vous ANDles deux numéros, vous récupérez l'original.

Pour les nombres qui ne sont pas des puissances de 2, les autres bits ne seront pas retournés, donc le ANDne donne pas le nombre d'origine.

Simplement, si n est une puissance de 2, cela signifie qu'un seul bit est mis à 1 et les autres à 0:

00000...00001 = 2 ^ 0
00000...00010 = 2 ^ 1
00000...00100 = 2 ^ 2
00000...01000 = 2 ^ 3
00000...10000 = 2 ^ 4

and so on ...

et parce que -nest un complément à 2 de n(cela signifie que le seul bit qui est 1 reste tel quel et que les bits sur le côté gauche de ce bit sont assis à 1, ce qui n'a pas vraiment d'importance puisque le résultat de l'opérateur AND &sera 0 si l'un des deux bits est zéro):

000000...000010000...00000 <<< n
&
111111...111110000...00000 <<< -n
--------------------------
000000...000010000...00000 <<< n

Montré par exemple:

8 en hexadécimal = 0x000008

-8 en hexadécimal = 0xFFFFF8

8 et -8 = 0x000008