Counting Bits

Q: Wie hoch ist die Zeitkomplexität von Counting Bits?

Die beste Lösung läuft in O(n) Zeit: Jeder der n+1 Einträge ergibt sich aus einem früheren Eintrag durch eine Addition. Die Bits jeder Zahl einzeln zu zählen, dauert O(n log n). Beide benötigen zusätzlich zum Ausgabe-Array O(1) Speicher.

Q: Gibt es eine weitere O(n)-Rekurrenz zum Zählen von Bits?

Ja. i & (i-1) löscht das niedrigstwertige 1-Bit von i , also gilt bits[i] = bits[i & (i-1)] + 1 für jedes i , das mindestens 1 ist. Für 12 ( 1100 ) ist 12 & 11 gleich 8 ( 1000 ), das eine 1 enthält, also hat 12 zwei.

Q: Kann ich eine integrierte Popcount-Funktion verwenden?

Für jede Zahl eine entsprechende Funktion aufzurufen, etwa Integer.bitCount in Java oder __builtin_popcount in C und C++, liefert die richtige Antwort. In Vorstellungsgesprächen wird meist nach der Variante ohne diese Funktion gefragt, denn bei dieser Aufgabe geht es darum, bereits berechnete Antworten wiederzuverwenden.

LeichtBitmanipulation Dynamische Programmierung

+10

Gegeben eine ganze Zahl n, die 0 oder größer ist, gib ein Array mit n+1 Einträgen zurück, wobei der Eintrag i für jedes i von 0 bis n die Anzahl der Einsen in der Binärdarstellung von i angibt.

Funktion

countBits(n: integer) → integer-array

ninteger: die letzte zu zählende Zahl, 0 oder mehr
Gibt zurückinteger-array: ein Array mit n+1 Zählwerten, wobei der Eintrag i die Anzahl der 1-Bits in i angibt

Einschränkungen

0 ≤ n ≤ 2 × 10⁴

Beispiele

Eingabe: n = 2
Ausgabe: [0, 1, 1]
Erklärung: Im Binärsystem ist 0 0, 1 ist 1 und 2 ist 10: keine Einsen, dann eine, dann eine.

Eingabe: n = 5
Ausgabe: [0, 1, 1, 2, 1, 2]
Erklärung: 3 ist 11 und 5 ist 101, jeweils mit zwei Einsen; 4 ist 100, mit einer. Zusammen mit 0, 1 und 2 aus dem ersten Beispiel ergeben sich die Anzahlen 0, 1, 1, 2, 1, 2.

Weiterführende Frage

Kannst du das ganze Array in O(n)-Zeit füllen, ohne eine eingebaute Funktion zum Zählen von Bits zu verwenden und ohne jede Zahl von Grund auf neu zu zählen?

Tipps

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

0 von 3 geöffnet

Lösung

Jede Zahl von Grund auf neu zu zählen, wiederholt Arbeit: 13 ist 1101, die Bits von 6 (110) mit einer zusätzlichen Ziffer am Ende. Fülle die Antworten in aufsteigender Reihenfolge aus, und jeder Eintrag verwendet mit einer Addition einen kleineren wieder.

Zähle die Bits jeder Zahl

Idee

Zähle die 1-Bits jeder Zahl direkt: Addiere x & 1 zu einem Zähler, verschiebe x um eine Stelle nach rechts und höre bei 0 auf. Bei 13 (1101) ergeben die Bits 1, 0, 1, 1, also ist die Anzahl 3.

Eine Zahl bis n hat etwa log2 n Binärstellen, daher beträgt die Laufzeit O(n log n): etwa 20.000 × 15 = 300.000 Schritte für n = 2 × 10^4.

Algorithmus

Erstelle eine leere Ergebnisliste.
Setze für jedes i von 0 bis n count auf 0 und x auf i.
Solange x größer als 0 ist, addiere x & 1 zu count und verschiebe x um eins nach rechts.
Füge count zum Ergebnis hinzu.
Gib das Ergebnis zurück.

def countBits(n):
    bits = []
    for i in range(n + 1):
        count = 0
        x = i
        while x > 0:
            count += x & 1  # the lowest bit
            x >>= 1         # shift it out
        bits.append(count)
    return bits

Auf der Hälfte der Zahl aufbauen

Idee

Wenn man i um eins nach rechts verschiebt, wird seine letzte Binärziffer gelöscht, und i & 1 ist diese Ziffer. i hat also die Einsen von i >> 1 plus seine letzte Ziffer: bits[i] = bits[i >> 1] + (i & 1).

Für jedes i ab 1 ist i >> 1 kleiner als i. Wenn man das Array also von links nach rechts füllt und bei bits[0] = 0 beginnt, ist der Eintrag, den man ausliest, immer bereits verfügbar. Für n = 5 gilt: bits[3] = bits[1] + 1 = 2, bits[4] = bits[2] + 0 = 1, bits[5] = bits[2] + 1 = 2.

Jeder Eintrag erfordert eine Verschiebung, ein AND und eine Addition: Laufzeit O(n) und kein zusätzlicher Speicher über die Ausgabe hinaus.

Algorithmus

Erstelle ein Array bits mit n+1 Nullen. bits[0] bleibt 0.
Setze für i von 1 bis n bits[i] auf bits[i >> 1] + (i & 1).
Gib bits zurück.

def countBits(n):
    bits = [0] * (n + 1)
    for i in range(1, n + 1):
        # i >> 1 is i without its last bit, and i & 1 is that last bit
        bits[i] = bits[i >> 1] + (i & 1)
    return bits

Stolperfallen und Grenzfälle

n Einträge statt n+1 zurückgeben. Für n = 0 lautet die Antwort [0].
Operatorrangfolge. In Python, C, Java und JavaScript bindet + stärker als &, daher bedeutet bits[i >> 1] + i & 1 (bits[i >> 1] + i) & 1. Behalte die Klammern um (i & 1) bei.
bits[i-1] statt bits[i >> 1] nachschlagen. Zwischen Nachbarzahlen gibt es keine einfache Regel: 7 ist 111 mit drei Einsen und 8 ist 1000 mit einer.
In Lua und R beginnen Arrays bei 1. Daher befindet sich die Anzahl für i am Index i+1 und der Nachschlageindex für i >> 1 bei floor(i/2) + 1. Lua 5.1 hat keinen Shift-Operator, teile also mit math.floor(i / 2) durch 2.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität von Counting Bits?

Die beste Lösung läuft in O(n) Zeit: Jeder der n+1 Einträge ergibt sich aus einem früheren Eintrag durch eine Addition. Die Bits jeder Zahl einzeln zu zählen, dauert O(n log n). Beide benötigen zusätzlich zum Ausgabe-Array O(1) Speicher.

Gibt es eine weitere O(n)-Rekurrenz zum Zählen von Bits?

Ja. i & (i-1) löscht das niedrigstwertige 1-Bit von i, also gilt bits[i] = bits[i & (i-1)] + 1 für jedes i, das mindestens 1 ist. Für 12 (1100) ist 12 & 11 gleich 8 (1000), das eine 1 enthält, also hat 12 zwei.

Kann ich eine integrierte Popcount-Funktion verwenden?

Für jede Zahl eine entsprechende Funktion aufzurufen, etwa Integer.bitCount in Java oder __builtin_popcount in C und C++, liefert die richtige Antwort. In Vorstellungsgesprächen wird meist nach der Variante ohne diese Funktion gefragt, denn bei dieser Aufgabe geht es darum, bereits berechnete Antworten wiederzuverwenden.

def countBits(n):
    # Schreibe hier den Code

Test #1

Test #2

Argument

n = 2

Erwartete Ausgabe

[0, 1, 1]