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

84

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?

David Weng
quelle
2
Das neue Tag sollte ein Hinweis sein. :)
bzlm
10
Hier ist die Antwort: stackoverflow.com/questions/600293/…
Jacob Mattison
2
Folgen Sie den Bits. Übrigens zählt es auch Null als Zweierpotenz. Die Formel (n & (n - 1)) == 0funktioniert auch (sie entfernt das Bit niedrigster Ordnung, wenn keine Bits mehr vorhanden sind, wurde zuerst höchstens 1 Bit gesetzt).
Harold
3
Ja, ich bekenne mich schuldig, solchen Code verwendet zu haben. Es gibt eine Reihe solcher Tricks, die Sie spielen können, solange Sie wissen, dass Sie sich mit der Komplementarithmetik von 2 befassen und die verschiedenen Konvertierungs- und Überlauf-Fallstricke kennen. Für zusätzliche Gutschriften finden Sie heraus, wie Sie auf die nächsthöhere Zweierpotenz oder vielleicht auf die Zweierpotenz aufrunden können - Dinge, die in einigen Quartalen mit überraschender Häufigkeit erledigt werden müssen.
Hot Licks
1
Warten Sie, lesen heutzutage alle aus der Quelle java.util.Random? (Ich habe das vor ein paar Monaten gelesen und erinnere mich an ein paar Fragen dazu auf SO seitdem.)
Mateen Ulhaq

Antworten:

48

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.

Mike Samuel
quelle
Und es gibt einen Trick, um das niedrigstwertige 1-Bit zu isolieren.
Hot Licks
2
Was (0 & -0) == 0, der unmittelbar vorhergehende Aussage ist if (n <= 0) throw .... Dies bedeutet, dass die zu testende Zahl zu diesem Zeitpunkt niemals 0 (oder negativ) sein wird.
Benutzer
1
@ Michael, ganz richtig. Ich beantwortete die Frage im Titel nicht kritisierend, Random.javadie ich nicht gelesen habe.
Mike Samuel
1
@ Mike, das merke ich; Ich denke jedoch nicht, dass die Aussage im Kommentar im Code (die in der Frage enthalten ist und die Grundlage für die Frage im Titel bildet) für sich allein steht, wenn sie nicht im Kontext der kurz zuvor festgelegten Voraussetzungen gesehen wird dazu im Code. Wenn Sie sich nur die hier veröffentlichte Frage ansehen , wissen wir nicht einmal, um welchen Typ es sich nhandelt. Ich habe diese Annahme nicht überprüft, bezweifle aber irgendwie, dass sich a doublegenauso verhalten würde.
Benutzer
3
@Michael, wir können dem Typ von ziemlich gute Grenzen setzen, nda diese Frage das "Java" -Tag hat. &ist nicht auf doubleoder floatin Java definiert. Es ist nur für Integer-Typen und Boolesche Werte definiert. Da dies -nicht für Boolesche Werte definiert ist, können wir sicher schließen, dass dies nein integraler Bestandteil ist.
Mike Samuel
95

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

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.

Johan
quelle
8

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.

Finsternis
quelle
4

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

Austin Salonen
quelle
4

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
Eng.Fouad
quelle
0

Beispiel gezeigt:

8 in hex = 0x000008

-8 in hex = 0xFFFFF8

8 & -8 = 0x000008

John B.
quelle