Si il y a une puissance de 2, on a du ou du . Facile !

Question

Ligne 294 de java.util.Source aléatoires dit

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

Pourquoi est-ce?

Answer 1

Parce qu'en complément de 2, -n est ~n+1.

Si n est une puissance de 2, alors il n'a qu'un ensemble de bits. Donc, ~n a tous les bits sauf que l'un. Ajouter 1, et que vous définissez le bit spécial de nouveau, en s'assurant qu' n & (that thing) est égal à n.

L'inverse est également vrai, car 0 et les nombres négatifs ont été écartés par la ligne précédente en ce que la source Java. Si n a plus d'un ensemble de bits, puis l'un d'eux est le plus élevé de bits. Ce bit sera pas être défini par l' +1 car il y a moins clair peu à "absorber":

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

Answer 2

La description n'est pas tout à fait exact; (0 & -0) == 0 mais 0 n'est pas une puissance de deux. Une meilleure façon de dire qu'il est

((n & -n) == n) lorsque n est une puissance de deux, ou de la forme négative d'une puissance de deux, ou de zéro.

Si n est une puissance de deux, puis n en binaire est un seul 1 suivi par des zéros. -n en complément à deux est l'inverse de + 1, de sorte que les bits de lignes ainsi

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

Pour voir pourquoi ce travail, envisager en complément à deux inverses + 1, -n == ~n + 1

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

depuis que vous portez l'un tout le chemin à travers lors de l'ajout d'un pour obtenir le complément à deux.

Si n étaient rien d'autre qu'une puissance de deux† le résultat pourrait être manquant un peu parce que le complément à deux n'aurait pas le bit le plus élevé en raison de que procéder.

† ou nul ou négatif, d'une puissance de deux ... comme expliqué dans la partie supérieure.

Answer 3

Vous avez besoin de regarder les valeurs de bitmaps de voir pourquoi ce qui est vrai:

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

De sorte que si les deux champs sont 1 un 1 en sortir.

Maintenant n un complément de 2. Il change tous les 0 de 1 et on ajoute 1.

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

Cependant

8 = 00001000
-8 = 11110111 + 1 = 11111000 

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

Seulement pour des puissances de 2 (n & -n) n.
C'est parce que d'une puissance de 2 est représenté par un seul bit dans un long de la mer de zéro. La négation donnera l'exact opposé, un seul zéro (à l'endroit où l'1) dans une mer de 1. L'ajout de 1 maj le bas dans l'espace où le zéro est.
Et La bit-à-bit " et " ( & ) filtre l'1 de nouveau.

Answer 4

En complément à deux de la représentation, la chose unique au sujet de puissances de deux, c'est qu'ils se composent de tous les 0 bits, sauf pour la kième bits, où n = 2^k:

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

Pour obtenir une valeur négative en complément à deux, vous retournez tous les morceaux et les ajouter. Pour des puissances de deux, cela signifie que vous obtenez un tas de 1s sur la gauche jusqu'à et y compris le 1er bit de la valeur positive, et puis un groupe des 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 de la colonne 2 & 4 va être la même que la colonne 2.

Si vous regardez les autres valeurs manquantes à partir de ce tableau, vous pouvez voir pourquoi il ne tient pas pour rien, mais 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 et-n (pour n > 0) ne jamais avoir 1 ensemble de bits, et que le bit le moins significatif de bit dans n. Pour tous les nombres qui sont des puissances de deux, le moins significatif de bit est le seul bit. Pour tous les autres nombres, il n'y a plus d'un ensemble de bits, dont seuls les moins importants seront mis dans le résultat.

Answer 5

C'est une propriété de puissances de 2 et de leur en complément à deux.

Par exemple, prendre 8:

8  = 0b00001000

-8 = 0b11111000

Le calcul du complément à deux:

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

AND 8    : 0b00001000

Pour des puissances de 2, seul un bit sera fixé afin d'ajouter sera la cause de la n^ième bit de 2ⁿ (l'un continue comptable à la n^ième bit). Puis, quand vous AND les deux chiffres, vous obtenez l'arrière d'origine.

Pour les nombres qui ne sont pas des puissances de 2, les autres bits ne sera pas obtenir renversé de sorte que le AND ne donne pas le nombre d'origine.