Number of 1 Bits

Q: Wie hoch ist die Zeitkomplexität von „Number of 1 Bits“?

Die Schiebe-Schleife läuft einmal pro Binärziffer: O(log n) , hier höchstens 31 Schritte. Die n & (n-1) -Schleife läuft einmal pro gesetztem Bit: O(k) , wobei k die Antwort ist. Beide benötigen zusätzlichen Speicherplatz von O(1) .

LeichtBitmanipulation

+10

Du erhältst eine nichtnegative ganze Zahl n. Schreibe n in Binärdarstellung und gib zurück, wie viele seiner Ziffern 1 sind. Diese Anzahl wird auch Anzahl der gesetzten Bits, Popcount oder Hamming-Gewicht genannt. Zum Beispiel ist 6 in Binärdarstellung 110, also hat es zwei 1-Bits.

Funktion

hammingWeight(n: integer) → integer

ninteger: eine nichtnegative Ganzzahl, die in einen vorzeichenbehafteten 32-Bit-Integer passt
Gibt zurückinteger: Anzahl der 1-Ziffern in der Binärdarstellung von n

Einschränkungen

0 ≤ n ≤ 2³¹-1

Beispiele

Eingabe: n = 11
Ausgabe: 3
Erklärung: 11 ist 1011 im Binärsystem, also 8 + 2 + 1. Drei seiner vier Binärziffern sind 1, daher ist die Antwort 3.

Eingabe: n = 128
Ausgabe: 1
Erklärung: 128 ist 2^7, geschrieben als 10000000: eine einzelne 1, gefolgt von Nullen, also ist die Antwort 1.

Weiterführende Frage

Wenn diese Funktion millionenfach ausgeführt würde, wie könntest du die Bits einer 32-Bit-Zahl mit vier Nachschlägen in einer Tabelle mit 256 vorberechneten Anzahlen zählen?

Tipps

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

0 von 3 geöffnet

Lösung

Durchlaufe die Binärziffern von n, ohne einen String zu erstellen. Das Lesen des letzten Bits und das Wegschieben benötigt einen Schritt pro Binärziffer, bis zu 31. Das Löschen des niedrigsten 1-Bits mit n & (n-1) benötigt einen Schritt pro 1-Bit, genau so viele wie das Ergebnis.

Überprüfe das letzte Bit und verschiebe es nach rechts

Idee

n & 1 ist die letzte Binärziffer von n: 1, wenn n ungerade ist, 0, wenn es gerade ist. Addiere sie zur Anzahl. Dann entfernt n >> 1 diese Ziffer und rückt die nächste an die letzte Stelle; bei einer nicht-negativen Zahl entspricht das einer Division durch 2, abgerundet. Bei 11, 1011, lauten die letzten Bits 1, 1, 0 und 1, während n auf 0 schrumpft: drei 1-Bits.

Die Schleife endet, wenn n 0 ist, besucht also niemals führende Nullen: etwa log2(n) Schritte, 8 für 128 und höchstens 31. Sie speichert nur n und die Anzahl.

Algorithmus

Starte einen Zähler bei 0.
Solange n größer als 0 ist, addiere n & 1 zum Zähler.
Verschiebe n um ein Bit nach rechts.
Wenn n 0 erreicht, gib den Zähler zurück.

def hammingWeight(n):
    count = 0
    while n > 0:
        count += n & 1  # the last bit is 1 or 0
        n >>= 1         # drop the last bit
    return count

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

Idee

Durch das Subtrahieren von 1 wird das niedrigste 1-Bit zu 0 und jede darunterliegende 0 zu 1, während die darüberliegenden Bits unverändert bleiben. Daher behält n & (n-1) die oberen Bits bei und löscht das niedrigste 1-Bit: 12 ist 1100, 11 ist 1011, und 1100 & 1011 ist 1000.

Bei jedem Schritt wird genau ein 1-Bit entfernt, daher ist die Anzahl der Schritte, bis n 0 ist, die Antwort. Für 128 ist 1 Schritt statt 8 nötig, während 2^31-1 weiterhin 31 Schritte benötigt. Lua 5.1 hat keine Bitoperatoren, daher findet die entsprechende Version das niedrigste 1-Bit durch Halbieren und subtrahiert es; die Schleife läuft weiterhin einmal pro 1-Bit.

Algorithmus

Starte einen Zähler bei 0.
Solange n nicht 0 ist, ersetze n durch n & (n-1).
Erhöhe den Zähler nach jeder Ersetzung um 1.
Gib den Zähler zurück.

def hammingWeight(n):
    count = 0
    while n != 0:
        n &= n - 1  # turn off the lowest 1 bit
        count += 1
    return count

Stolperfallen und Grenzfälle

Schleife, solange n > 1. Die Schleife stoppt vor dem letzten 1-Bit und gibt für n = 1 0 zurück.
Division mit einer Gleitkommazahl. In JavaScript, Lua und R ist 11 / 2 gleich 5.5, und die folgenden Reste sind Brüche. Runde mit Math.floor, math.floor oder %/% ab oder verwende stattdessen eine Verschiebung.
n & 1 in Lua 5.1 schreiben. Lua 5.1 hat keine Bitoperatoren, daher wird der Code nicht kompiliert; verwende n % 2 und math.floor(n / 2).

Häufige Fragen3

Wie hoch ist die Zeitkomplexität von „Number of 1 Bits“?

Die Schiebe-Schleife läuft einmal pro Binärziffer: O(log n), hier höchstens 31 Schritte. Die n & (n-1)-Schleife läuft einmal pro gesetztem Bit: O(k), wobei k die Antwort ist. Beide benötigen zusätzlichen Speicherplatz von O(1).

Gibt es eine integrierte Funktion, die gesetzte Bits zählt?

Die meisten Sprachen bieten eine solche Funktion, oft unterstützt durch eine einzelne Prozessoranweisung: Integer.bitCount in Java, __builtin_popcount in GCC, bits.OnesCount in Go, count_ones in Rust und int.bit_count in Python 3.10 und späteren Versionen. Schreib in einem Vorstellungsgespräch die Schleife auf und erwähne die eingebaute Funktion.

Was ist der Unterschied zwischen Hamming-Gewicht und Hamming-Distanz?

Das Hamming-Gewicht einer Zahl gibt an, wie viele ihrer Binärstellen 1 sind. Genau das gibt dieses Problem zurück. Die Hamming-Distanz zwischen zwei Zahlen gibt an, an wie vielen Bitpositionen sie sich unterscheiden: Zähle die 1-Bits von a ^ b, da XOR genau an den Positionen eine 1 setzt, an denen sie sich unterscheiden.

def hammingWeight(n):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argument

n = 11

Erwartete Ausgabe