Power of Two

Q: Wie prüfst du, ob eine Zahl eine Zweierpotenz ist?

Gib true zurück, wenn n > 0 und n & (n-1) gleich 0 ist. Eine Zweierpotenz hat genau ein 1-Bit, und beim Subtrahieren von 1 wird dieses gelöscht, während nur die darunterliegenden Bits gesetzt werden, sodass das AND 0 ergibt. Halbiere n ohne Bitoperationen, solange es gerade ist, und prüfe, ob du bei 1 endest.

Q: Wie hoch ist die Zeitkomplexität von „Potenz von zwei“?

Die Prüfung n & (n-1) benötigt O(1) Zeit und Speicherplatz: einen Vergleich, eine Subtraktion und ein AND. Die Halbierungsschleife benötigt O(log n) Zeit, höchstens 31 Schritte für eine 32-Bit-Ganzzahl.

Q: Ist 1 eine Zweierpotenz? Ist 0 eine?

1 ist eine Zweierpotenz, denn 2^0 = 1 , und seine Binärdarstellung hat ein 1-Bit. 0 ist keine: Kein ganzzahliger Exponent ergibt 0, und die Zahl hat überhaupt kein 1-Bit. Negative Zahlen sind ebenfalls niemals Zweierpotenzen.

LeichtBitmanipulation

+10

Du erhältst eine ganze Zahl n. Gib true zurück, wenn n eine Zweierpotenz ist, das heißt, wenn n = 2^k für eine ganze Zahl k ≥ 0 gilt, und andernfalls false. Also zählen 1, 2, 4 und 8, während 0, 6 und alle negativen Zahlen nicht zählen.

Funktion

isPowerOfTwo(n: integer) → boolean

ninteger: die zu testende Ganzzahl, die null oder negativ sein kann
Gibt zurückboolean: wahr, wenn n gleich 2^k für ein k ≥ 0 ist, andernfalls falsch

Einschränkungen

-2³¹ ≤ n ≤ 2³¹-1

Beispiele

Eingabe: n = 16
Ausgabe: true
Erklärung: 16 = 2 × 2 × 2 × 2 = 2^4. In der Binärdarstellung ist es 10000, ein einzelnes 1-Bit.

Eingabe: n = 24
Ausgabe: false
Erklärung: 24 = 8 × 3. Durch Halbieren erhält man 12, 6 und dann 3, was ungerade, aber nicht 1 ist. In Binärdarstellung ist 24 11000, zwei 1-Bits.

Eingabe: n = 1
Ausgabe: true
Erklärung: 1 = 2^0, also ist es eine Zweierpotenz. Seine Binärdarstellung 1 hat genau ein 1-Bit.

+17 versteckte Tests beim Einreichen

Weiterführende Frage

Kannst du mit denselben Bit-Tricks ohne Schleife testen, ob n eine Potenz von vier ist?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Eine Zweierpotenz hat im Binärsystem eine feste Form: ein 1-Bit gefolgt von Nullen, wie 10000 für 16. Du kannst diese Form bestätigen, indem du n so lange halbierst, bis es ungerade wird; das dauert bis zu 31 Schritte. Oder du kannst sie mit n & (n-1) in einem Schritt bestätigen. Dabei wird das niedrigste 1-Bit gelöscht, und das Ergebnis ist nur dann 0, wenn dieses Bit das einzige war. Bei beiden Varianten kommt die Vorzeichenprüfung zuerst, denn null und negative Zahlen lassen den offensichtlichen Code scheitern.

So lange durch 2 teilen, wie die Zahl gerade ist

Idee

Wenn n = 2^k ist, kannst du es genau k‑mal durch 2 teilen und erhältst 1; alle Werte auf dem Weg dorthin sind gerade. Wenn n einen ungeraden Faktor größer als 1 hat, endet das Halbieren bei einer ungeraden Zahl, die nicht 1 ist. Für 16: 16, 8, 4, 2, 1, also ist die Antwort wahr. Für 24: 24, 12, 6, 3, und 3 ist ungerade, aber nicht 1, also ist die Antwort falsch.

Gib vor der Schleife false zurück, wenn n ≤ 0. Keine Zweierpotenz ist null oder negativ, und die Schleife würde bei 0 nie enden, weil 0 gerade ist und die Hälfte von 0 weiterhin 0 ist.

Bei jedem Schritt wird n halbiert, daher benötigt eine 32-Bit-Eingabe höchstens 31 Schritte: Zeitaufwand O(log n) und Speicherplatzbedarf O(1).

Algorithmus

Wenn n ≤ 0, gib false zurück.
Solange n gerade ist, teile es durch 2.
Gib zurück, ob n jetzt 1 ist.

def isPowerOfTwo(n):
    if n <= 0:
        return False
    while n % 2 == 0:
        n //= 2
    return n == 1

Das niedrigstwertige gesetzte Bit mit n & (n-1) löschen

Idee

Schreibt man eine Zweierpotenz binär, besteht sie aus einer einzelnen 1, auf die Nullen folgen: 16 ist 10000. Durch Subtraktion von 1 wird diese 1 zur 0 und jede darunterliegende 0 zur 1: 15 ist 01111. Die beiden Zahlen haben kein gemeinsames 1-Bit, daher ist 16 & 15 gleich 0.

Jede andere positive Zahl hat mindestens zwei 1-Bits. Durch Subtraktion von 1 werden nur das niedrigste 1-Bit und die darunterliegenden Nullen verändert. Daher kommt jedes höhere 1-Bit in beiden Zahlen vor, und das AND ist nicht 0. Für 24, also 11000, erhält man 23 = 10111, und 24 & 23 ist 10000, also 16.

Prüft zuerst n > 0. 0 & -1 ist 0, und bei 32-Bit-Arithmetik ist -2^31 ein einzelnes 1-Bit, auf das 31 Nullen folgen. Allein anhand des AND würde man also beide für Zweierpotenzen halten. Der gesamte Test besteht aus einem Vergleich, einer Subtraktion und einem AND: Zeit- und Speicheraufwand O(1). Lua 5.1 hat keinen AND-Operator, daher bildet der Lua-Code das AND Bit für Bit, mit bis zu 31 Schritten für ein 32-Bit-n; der Test ist derselbe.

Algorithmus

Wenn n ≤ 0 gilt, gib false zurück.
Berechne n & (n-1), also n mit gelöschtem niedrigstem 1-Bit.
Gib zurück, ob dieses Ergebnis 0 ist.

def isPowerOfTwo(n):
    # One set bit: n - 1 flips it and every bit below, so the AND is 0.
    return n > 0 and n & (n - 1) == 0

Stolperfallen und Grenzfälle

Der Bit-Test besteht aus einer Zeile, und die meisten Fehler betreffen Eingaben, für die er nicht ausgelegt ist.

Die Vorzeichenprüfung überspringen. 0 & (0-1) ergibt 0, also besteht 0 den AND-Test. Bei 32-Bit-Ganzzahlen besteht auch -2^31 den Test, weil seine Binärdarstellung aus einem einzelnen 1-Bit besteht. Beide müssen false zurückgeben.
Die Halbierungsschleife mit 0 ausführen. Null ist gerade, und halbiert ergibt sie wieder 0, sodass die Schleife nie endet.
Die Klammern weglassen. == bindet stärker als &, daher wird in C, C++ und JavaScript n & n - 1 == 0 als n & ((n - 1) == 0) gelesen und liefert ohne Fehlermeldung das falsche Ergebnis; Java und C# weisen es als Typfehler zurück. Schreibe (n & (n - 1)) == 0.
Logarithmen verwenden. Bei doppelter Genauigkeit ergibt log(536870912) / log(2) den Wert 29.000000000000004 statt 29, sodass eine Prüfung auf eine ganze Zahl 2^29 als false einstuft.

Häufige Fragen4

Wie prüfst du, ob eine Zahl eine Zweierpotenz ist?

Gib true zurück, wenn n > 0 und n & (n-1) gleich 0 ist. Eine Zweierpotenz hat genau ein 1-Bit, und beim Subtrahieren von 1 wird dieses gelöscht, während nur die darunterliegenden Bits gesetzt werden, sodass das AND 0 ergibt. Halbiere n ohne Bitoperationen, solange es gerade ist, und prüfe, ob du bei 1 endest.

Warum löscht n & (n-1) das niedrigstwertige gesetzte Bit?

Beim Subtrahieren von 1 wird vom niedrigsten gesetzten Bit 1 geborgt: Dieses Bit wird zu 0 und jede darunterliegende 0 wird zu 1, während die höheren Bits unverändert bleiben. Durch die UND-Verknüpfung mit dem ursprünglichen Wert bleiben nur die Bits erhalten, die in beiden gesetzt sind; das sind genau die höheren Bits. Bei einer Zweierpotenz gibt es keine höheren Bits, daher ist das Ergebnis 0.

Wie hoch ist die Zeitkomplexität von „Potenz von zwei“?

Die Prüfung n & (n-1) benötigt O(1) Zeit und Speicherplatz: einen Vergleich, eine Subtraktion und ein AND. Die Halbierungsschleife benötigt O(log n) Zeit, höchstens 31 Schritte für eine 32-Bit-Ganzzahl.

Ist 1 eine Zweierpotenz? Ist 0 eine?

1 ist eine Zweierpotenz, denn 2^0 = 1, und seine Binärdarstellung hat ein 1-Bit. 0 ist keine: Kein ganzzahliger Exponent ergibt 0, und die Zahl hat überhaupt kein 1-Bit. Negative Zahlen sind ebenfalls niemals Zweierpotenzen.

Python

def isPowerOfTwo(n):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

n = 16

Erwartet

true