Counting Bits

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

Die beste Lösung benötigt O(n) Zeit: Jeder der n+1 Einträge ergibt sich aus einem vorherigen Eintrag durch eine Addition. Zählt man die Bits jeder Zahl einzeln, benötigt das O(n log n), da eine Zahl bis zu n etwa log2 n Binärstellen hat. Beide benötigen zusätzlich zum Ausgabe-Array O(1) Speicher.

Q: Warum funktioniert bits[i] = bits[i >> 1] + (i & 1) ?

i >> 1 ist i ohne die letzte Binärziffer, und i & 1 ist diese entfernte Ziffer. Die Anzahl der Einsen in i ist die Anzahl der Einsen in der kürzeren Zahl plus der letzten Ziffer. Bei 11, also 1011 , ist die kürzere Zahl 5 ( 101 , zwei Einsen) und die letzte Ziffer 1, also hat 11 drei Einsen.

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 , daher gilt bits[i] = bits[i & (i-1)] + 1 für jedes i größer oder gleich 1. Für 12 ( 1100 ) ist 12 & 11 gleich 8 ( 1000 ), das eine 1 enthält, also hat 12 zwei. Das ist genauso schnell wie die Verschiebungsregel und verwendet dieselbe Füllung von links nach rechts.

LeichtBitmanipulation Dynamische Programmierung

+10

Du erhältst eine ganze Zahl n, die mindestens 0 ist. Zähle für jede Zahl i von 0 bis n, wie viele Einsen vorkommen, wenn i binär dargestellt wird. Gib die Anzahlen als Array mit n+1 Einträgen zurück, wobei Eintrag i die Anzahl für die Zahl i enthält.

Funktion

countBits(n: integer) → integer-array

ninteger: die letzte zu zählende Zahl, 0 oder mehr
Gibt zurückinteger-array: ein Array aus 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. Das bedeutet 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, während 4 100 ist und eine einzelne 1 enthält. Zusammen mit 0, 1 und 2 aus dem ersten Beispiel lauten die Anzahlen für 0 bis 5: 0, 1, 1, 2, 1, 2.

+15 versteckte Tests beim Einreichen

Weiterführende Frage

Kannst du das gesamte Array in O(n)-Zeit füllen, ohne eine eingebaute Funktion zu verwenden, die Bits zählt, 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

Die 1en jeder Zahl einzeln zu zählen funktioniert, wiederholt aber Arbeit. 13 ist 1101 und 6 ist 110: Die Bits von 13 sind die Bits von 6 mit einer weiteren Ziffer am Ende. Wenn du die Antworten in aufsteigender Reihenfolge einträgst, steht die Anzahl, die du für i brauchst, bereits im Array, und jeder Eintrag erfordert eine Addition.

Zähle die Bits jeder Zahl

Idee

Nimm jede Zahl von 0 bis n und zähle ihre 1-Bits direkt. Das niedrigste Bit von x ist x & 1. Addiere es zu einem Zähler und verschiebe dann x mit x >> 1 nach rechts, sodass das nächste Bit zum niedrigsten wird. Beende den Vorgang, wenn x 0 erreicht.

Bei 13, also 1101, ergeben die Bits von rechts aus 1, 0, 1, 1, die Anzahl ist also 3. Für jede Zahl wird pro Binärziffer ein Schritt benötigt, und eine Zahl bis n hat etwa log2 n Ziffern.

Damit beträgt die Laufzeit insgesamt O(n log n). Für n = 2 × 10^4 sind das etwa 20.000 × 15 = 300.000 Schritte, was schnell genug läuft. Trotzdem wird Arbeit verschwendet: Beim Zählen von 13 werden alle Schritte wiederholt, die du bereits für 6 ausgeführt hast. Der Speicherbedarf beträgt O(1), abgesehen vom Ausgabe-Array.

Algorithmus

Beginne mit einer leeren 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 eine Stelle 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

Verdopple die Hälfte der Zahl

Idee

Eine Verschiebung von i um eins nach rechts löscht seine letzte Binärziffer. Daher hat i genau die 1-Bits von i >> 1, plus ein weiteres, wenn seine letzte Ziffer 1 ist. Diese letzte Ziffer ist i & 1, woraus sich die Regel bits[i] = bits[i >> 1] + (i & 1) ergibt.

Für jedes i ab 1 ist i >> 1 kleiner als i. Wenn du das Array von links nach rechts füllst und mit bits[0] = 0 beginnst, ist der Eintrag, den du nachschlägst, immer bereits ausgefüllt. Das ist dynamische Programmierung: Jede Antwort wird aus einer kleineren aufgebaut.

Für n = 5: bits[1] = bits[0] + 1 = 1, bits[2] = bits[1] + 0 = 1, 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. Daher beträgt die Laufzeit O(n), und über die Ausgabe hinaus wird kein Speicher benötigt.

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

Die Regel passt auf eine Zeile, deshalb verstecken sich die Fehler darin.

Das Array hat n+1 Einträge, nicht n. Für n = 0 lautet die Antwort [0]: ein Eintrag für die Zahl 0.
Operatorrangfolge. In Python, C, Java und JavaScript bindet + stärker als &, daher wird bits[i >> 1] + i & 1 als (bits[i >> 1] + i) & 1 gelesen. Behalte die Klammern um (i & 1) bei.
Auf bits[i-1] statt auf bits[i >> 1] zugreifen. Nachbarn haben keine einfache gemeinsame Regel: 7 ist 111 mit drei Einsen, und 8 ist 1000 mit einer.
In Lua und R beginnen Arrays bei 1, daher steht die Anzahl für i am Index i+1, und der Zugriff auf i >> 1 erfolgt am Index floor(i/2) + 1. Das Lua des Runners hat keinen Shift-Operator, also halbiere mit math.floor(i / 2).
Jede Zahl in eine Binärzeichenfolge umzuwandeln und die 1-Zeichen zu zählen, ergibt die richtige Antwort, erstellt aber für jede Zahl eine neue Zeichenfolge.

Häufige Fragen4

Wie hoch ist die zeitliche Komplexität von Counting Bits?

Die beste Lösung benötigt O(n) Zeit: Jeder der n+1 Einträge ergibt sich aus einem vorherigen Eintrag durch eine Addition. Zählt man die Bits jeder Zahl einzeln, benötigt das O(n log n), da eine Zahl bis zu n etwa log2 n Binärstellen hat. Beide benötigen zusätzlich zum Ausgabe-Array O(1) Speicher.

Warum funktioniert <code>bits[i] = bits[i >> 1] + (i & 1)</code>?

i >> 1 ist i ohne die letzte Binärziffer, und i & 1 ist diese entfernte Ziffer. Die Anzahl der Einsen in i ist die Anzahl der Einsen in der kürzeren Zahl plus der letzten Ziffer. Bei 11, also 1011, ist die kürzere Zahl 5 (101, zwei Einsen) und die letzte Ziffer 1, also hat 11 drei Einsen.

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

Ja. i & (i-1) löscht das niedrigstwertige 1-Bit von i, daher gilt bits[i] = bits[i & (i-1)] + 1 für jedes i größer oder gleich 1. Für 12 (1100) ist 12 & 11 gleich 8 (1000), das eine 1 enthält, also hat 12 zwei. Das ist genauso schnell wie die Verschiebungsregel und verwendet dieselbe Füllung von links nach rechts.

Kann ich eine integrierte Popcount-Funktion verwenden?

Die meisten Sprachen haben eine solche Funktion, zum Beispiel Integer.bitCount in Java oder __builtin_popcount in C und C++, und sie für jede Zahl aufzurufen, ergibt eine korrekte Antwort. Interviewer fragen gewöhnlich nach der Variante ohne diese Funktion, weil es bei dem Problem darum geht, bereits berechnete Antworten wiederzuverwenden. Die Rekurrenz funktioniert auch in Sprachen ohne eine solche Funktion.

Python

def countBits(n):
    # Schreibe hier Code

Testfälle

Fall 1

Fall 2

Eingabe

n = 2

Erwartet

[0, 1, 1]