Warum, wenn (n & -n) == n, dann ist n eine Potenz von 2?

Zeile 294 von java.util.Random Quelle sagt

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

Warum ist das?

Die Beschreibung ist nicht ganz korrekt, da (0 & -0) == 00 keine Zweierpotenz ist. Ein besserer Weg, es zu sagen, ist

((n & -n) == n) wenn n eine Zweierpotenz oder das Negativ einer Zweierpotenz oder Null ist.

Wenn n eine Zweierpotenz ist, ist n in binär eine einzelne 1, gefolgt von Nullen. -n im Zweierkomplement ist die Umkehrung + 1, so dass die Bits so ausgerichtet sind

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

Um zu sehen, warum diese Arbeit funktioniert, betrachten Sie das Zweierkomplement als invers + 1, -n == ~n + 1

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

da Sie die eine vollständig durchtragen, wenn Sie eine hinzufügen, um die Ergänzung der beiden zu erhalten.

Wenn n etwas anderes als eine Zweierpotenz wäre †, würde das Ergebnis ein wenig fehlen, da das Zweierkomplement aufgrund dieses Übertrags nicht das höchste gesetzte Bit hätte.

† - oder Null oder ein Negativ einer Zweierpotenz ... wie oben erläutert.

Denn in 2er Komplement -nist ~n+1.

Wenn neine Potenz von 2 ist, ist nur ein Bit gesetzt. Also ~nsind alle Bits außer diesem gesetzt. Wenn Sie 1 hinzufügen, setzen Sie das spezielle Bit erneut und stellen sicher, dass n & (that thing)es gleich ist n.

Das Umgekehrte gilt auch, weil 0 und negative Zahlen in der vorherigen Zeile dieser Java-Quelle ausgeschlossen wurden. Wenn nmehr als ein Bit gesetzt ist, ist eines davon das höchste dieser Art. Dieses Bit wird von nicht gesetzt, +1da es ein niedrigeres klares Bit gibt, um es zu "absorbieren":

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

Sie müssen die Werte als Bitmaps betrachten, um festzustellen, warum dies der Fall ist:

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

Nur wenn beide Felder 1 sind, wird eine 1 ausgegeben.

Jetzt macht -n eine 2er-Ergänzung. Es ändert alles 0in 1und es fügt 1 hinzu.

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

jedoch

8 = 00001000
-8 = 11110111 + 1 = 11111000 

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

Nur für Potenzen von 2 wird (n & -n)n sein.
Dies liegt daran, dass eine Potenz von 2 als ein einzelnes gesetztes Bit in einem langen Meer von Nullen dargestellt wird. Die Negation ergibt genau das Gegenteil, eine einzelne Null (an der Stelle, an der sich die 1 befand) in einem Meer von Einsen. Durch Hinzufügen von 1 werden die unteren in den Bereich verschoben, in dem sich die Null befindet.
Und das bitweise und (&) filtert die 1 erneut heraus.

In der Zweierkomplementdarstellung besteht das Einzigartige an Zweierpotenzen darin, dass sie aus allen 0 Bits bestehen, mit Ausnahme des k-ten Bits, wobei n = 2 ^ k:

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

Um einen negativen Wert im Zweierkomplement zu erhalten, drehen Sie alle Bits um und fügen eins hinzu. Für Zweierpotenzen bedeutet dies, dass Sie links eine Reihe von Einsen bis einschließlich des 1-Bits erhalten, das sich im positiven Wert befand, und dann rechts eine Reihe von Nullen:

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

Sie können leicht erkennen, dass das Ergebnis der Spalten 2 und 4 mit dem der Spalte 2 übereinstimmen wird.

Wenn Sie sich die anderen Werte ansehen, die in dieser Tabelle fehlen, können Sie sehen, warum dies nur für die Zweierpotenzen gilt:

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 hat (für n> 0) immer nur 1 Bit gesetzt, und dieses Bit ist das niedrigstwertige gesetzte Bit in n. Für alle Zahlen, die Zweierpotenzen sind, ist das niedrigstwertige gesetzte Bit das einzige gesetzte Bit. Für alle anderen Zahlen ist mehr als ein Bit gesetzt, von denen im Ergebnis nur die niedrigstwertige gesetzt wird.

Es ist Eigentum von Zweierpotenzen und deren Zweierkomplement .

Nehmen Sie zum Beispiel 8:

8  = 0b00001000

-8 = 0b11111000

Berechnung des Zweierkomplements:

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

AND 8    : 0b00001000

Bei Potenzen von 2 wird nur ein Bit gesetzt, so dass durch Hinzufügen das n- ^te Bit von 2 ⁿ gesetzt wird (dasjenige wird weiter zum n- ^ten Bit übertragen). Wenn Sie dann ANDdie beiden Zahlen, erhalten Sie das Original zurück.

Bei Zahlen, die keine Zweierpotenzen sind, werden andere Bits nicht umgedreht, sodass die ANDnicht die ursprüngliche Zahl ergibt.

Wenn n eine Potenz von 2 ist, bedeutet dies einfach, dass nur ein Bit auf 1 gesetzt ist und die anderen Nullen sind:

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

and so on ...

und weil -nein 2er-Komplement von ist n(das bedeutet, dass das einzige Bit, das 1 ist, so bleibt, wie es ist, und die Bits auf der linken Seite dieses Bits auf 1 sitzen, was eigentlich keine Rolle spielt, da das Ergebnis des AND-Operators &0 ist, wenn eines der beiden Bits ist Null):

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

Beispiel gezeigt:

8 in hex = 0x000008

-8 in hex = 0xFFFFF8

8 & -8 = 0x000008