n & (n-1) was macht dieser Ausdruck? [duplicate]

Lesezeit: 2 Minuten

Benutzeravatar von Vishwanath Dalvi
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?

  • Ü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

Benutzeravatar von paxdiablo
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

  • Es ist ein Problem von leetcode

    – Jerry An

    9. Februar 2021 um 9:06 Uhr

Benutzeravatar von Paul R
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);
}

Benutzeravatar von sarnold
Sarnold

Es prüft, ob n eine Potenz von 2 ist: Was macht der bitweise Code “$n & ($n – 1)”?

Neils Benutzeravatar
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.

1408010cookie-checkn & (n-1) was macht dieser Ausdruck? [duplicate]

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy