Mögliche Duplikate:
Frage zur Berechnung, ob Zahl eine Potenz von 2 ist
Was macht diese Funktion?
n & (n-1)
– wo kann dieser Ausdruck verwendet werden?
Vishwanath Dalvi
Mögliche Duplikate:
Frage zur Berechnung, ob Zahl eine Potenz von 2 ist
Was macht diese Funktion?
n & (n-1)
– wo kann dieser Ausdruck verwendet werden?
paxdiablo
Es wird herausgefunden, ob n
ist entweder 0 oder eine exakte Zweierpotenz.
Es funktioniert, weil eine binäre Zweierpotenz von der Form ist 1000...000
und das Subtrahieren von eins ergibt 111...111
. Dann, wenn Sie UND diese zusammen, erhalten Sie Null, wie zum Beispiel mit:
1000 0000 0000 0000
& 111 1111 1111 1111
==== ==== ==== ====
= 0000 0000 0000 0000
Jeder Nicht-Potenz-von-Zwei-Eingabewert (außer Null) wird nicht geben Ihnen Null, wenn Sie diese Operation ausführen.
Probieren wir zum Beispiel alle 4-Bit-Kombinationen aus:
<----- binary ---->
n n n-1 n&(n-1)
-- ---- ---- -------
0 0000 0111 0000 *
1 0001 0000 0000 *
2 0010 0001 0000 *
3 0011 0010 0010
4 0100 0011 0000 *
5 0101 0100 0100
6 0110 0101 0100
7 0111 0110 0110
8 1000 0111 0000 *
9 1001 1000 1000
10 1010 1001 1000
11 1011 1010 1010
12 1100 1011 1000
13 1101 1100 1100
14 1110 1101 1100
15 1111 1110 1110
Nur das sieht man 0
und die Zweierpotenzen (1
, 2
, 4
und 8
) ergeben a 0000/false
Bitmuster, alle anderen sind ungleich Null oder true
.
Wie kommt es, dass 7 und -1 beide 0111 haben?
– Sofas1
16. Oktober 2018 um 3:59 Uhr
n & (n-1)
hilft bei der Identifizierung des Werts des letzten Bits. Da das niederwertigste Bit für n und n-1 entweder (0 und 1) oder (1 und 0) ist. Siehe obige Tabelle. (n & (n-1)) == 0
prüft nur, ob n eine Potenz von 2 oder 0 ist.
– Sofas1
16. Oktober 2018 um 7:57 Uhr
Paul R
Es gibt 0 zurück, wenn n eine Potenz von 2 ist (NB: funktioniert nur für n > 0
). Sie können also wie folgt auf eine Potenz von 2 testen:
bool isPowerOfTwo(int n)
{
return (n > 0) && ((n & (n - 1)) == 0);
}
Sarnold
Es prüft, ob n eine Potenz von 2 ist: Was macht der bitweise Code “$n & ($n – 1)”?
Neil
Es ist eine bitweise Operation zwischen einer Zahl und ihrer vorherigen Zahl. Dieser Ausdruck könnte nur dann falsch sein, wenn n eine Potenz von 2 ist, also überprüfen Sie im Wesentlichen, ob es keine Potenz von 2 ist.
Überprüfen Sie diese Frage: stackoverflow.com/questions/3265942/what-does-this-function-do/…
– Wladimir
13. Januar 2011 um 9:12 Uhr
@Paul R, für mich ist es kein Duplikat (wenn auch verwandt) – dieses kommt umgekehrt, könnte man sagen.
– Peter Török
13. Januar 2011 um 9:25 Uhr
Es verwandelt die rechte 1 in 0 des Binärmodus von n. Wenn das Ergebnis gleich 0 ist, bedeutet dies, dass es im Binärmodus von n nur eine 1 gibt, was bedeutet, dass n eine Potenz von 2 ist.
– Auf Wiedersehen
12. November 2019 um 12:34 Uhr