Bits zählen, fehlende Zahl und Bits umkehren
Berechnen Sie Bitanzahlen für 0..n mit DP und dem Trick des niedrigsten gesetzten Bits, finden Sie eine fehlende Zahl per XOR und kehren Sie die Bits einer 32-Bit-Ganzzahl um.
Bits zählen, fehlende Zahl und Bits umkehren ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 4 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Übersicht zum Problem des Bitzählens
Das Problem Counting Bits (LeetCode 338) lautet: Für ein gegebenes n sollen Sie ein Array ans der Größe n+1 zurückgeben, wobei ans[i] die Anzahl der 1-Bits in i angibt. Der naive Ansatz hat eine Laufzeit von O(n log n), da die Bits jeder Zahl einzeln gezählt werden. Der DP-Ansatz benötigt O(n), indem er die Beziehung zwischen i und seiner Halbierung beziehungsweise seinem niedrigsten gesetzten Bit ausnutzt.
Der DP liegen zwei wichtige Beobachtungen zugrunde: (1) i >> 1 entfernt das niedrigste Bit, daher gilt bits[i] = bits[i >> 1] + (i & 1). (2) Das Löschen des niedrigsten gesetzten Bits ergibt bits[i] = bits[i & (i-1)] + 1. Beide Ansätze benötigen O(n) Zeit und O(n) Speicher für das Ausgabe-Array.
def count_bits_v1(n):
# O(n log n): naive individual count
return [bin(i).count('1') for i in range(n + 1)]
def count_bits_dp(n):
# O(n): DP using right shift
dp = [0] * (n + 1)
for i in range(1, n + 1):
dp[i] = dp[i >> 1] + (i & 1) # i >> 1 drops last bit
return dp
def count_bits_dp2(n):
# O(n): DP using lowest-set-bit trick
dp = [0] * (n + 1)
for i in range(1, n + 1):
dp[i] = dp[i & (i - 1)] + 1 # i & (i-1) clears lowest set bit
return dp
n = 10
print('Naive:', count_bits_v1(n))
print('DP v1:', count_bits_dp(n))
print('DP v2:', count_bits_dp2(n))Warum die DP-Rekurrenzen funktionieren
Für die Rekurrenz mit Rechtsverschiebung dp[i] = dp[i >> 1] + (i & 1) gilt: Die Division durch 2 (Rechtsverschiebung) entfernt das letzte Bit. War das letzte Bit 1, erhöht sich die Anzahl um 1; war es 0, ändert sie sich nicht. Daher gilt bits[i] = bits[i // 2] + (i mod 2).
Für die Rekurrenz mit dem niedrigsten gesetzten Bit dp[i] = dp[i & (i-1)] + 1 gilt: i & (i-1) löscht das rechteste 1-Bit, enthält also ein gesetztes Bit weniger als i. Die Anzahl ist daher die Anzahl dieses reduzierten Werts plus 1. Beide Rekurrenzen verarbeiten i in aufsteigender Reihenfolge, sodass kleinere Teilprobleme immer zuerst gelöst werden.
# Trace both recurrences for i = 0..8
print('i | i>>1 | i&1 | dp[i>>1]+(i&1) | i&(i-1) | 1+dp[i&(i-1)]')
print('-' * 60)
dp = [0] * 9
for i in range(1, 9):
# Right shift method
v1 = dp[i >> 1] + (i & 1)
# Lowest set bit method
v2 = dp[i & (i - 1)] + 1
dp[i] = v1 # either works
print(f'{i:2d} ({bin(i)[2:]:4s}) | {i>>1:2d} | {i&1} | {v1} | {i&(i-1):2d} | {v2}')
print('\nFinal dp:', dp)Fehlende Zahl: XOR- und Summenansätze
Beim Problem Missing Number (LeetCode 268) enthält ein Array aus n verschiedenen Zahlen aus dem Bereich [0, n] genau eine fehlende Zahl. Beim XOR-Ansatz werden alle Indizes von 0 bis n mit allen Werten im Array per XOR verknüpft. Gleiche Paare heben sich auf, sodass die fehlende Zahl übrig bleibt. Beim Summenansatz gilt expected = n*(n+1)//2; zurückgegeben wird expected - sum(nums).
Beide Ansätze benötigen O(n) Zeit und O(1) Speicher. Der XOR-Ansatz ist in Sprachen mit Ganzzahlen fester Breite robuster, da ein möglicher Überlauf vermieden wird. In Python funktionieren beide Ansätze problemlos, weil Ganzzahlen beliebige Genauigkeit haben.
def missing_xor(nums):
n = len(nums)
result = n
for i, val in enumerate(nums):
result ^= i ^ val # each index i cancels its matching value
return result
def missing_sum(nums):
n = len(nums)
return n * (n + 1) // 2 - sum(nums)
test_cases = [
[3, 0, 1], # missing 2
[0, 1], # missing 2
[9,6,4,2,3,5,7,0,1], # missing 8
[0], # missing 1
]
for nums in test_cases:
print(f'{nums} => XOR={missing_xor(nums)}, Sum={missing_sum(nums)}')Bits einer 32-Bit-Ganzzahl umkehren
Das Problem Reverse Bits (LeetCode 190) verlangt, die Binärdarstellung einer vorzeichenlosen 32-Bit-Ganzzahl umzukehren. Beim iterativen Ansatz verarbeiten Sie jedes der 32 Bits der Eingabe von rechts nach links und setzen sie in umgekehrter Reihenfolge von links nach rechts in die Ausgabe. In jeder Iteration extrahieren Sie das rechteste Bit mit n & 1, verschieben die Ausgabe nach links, um Platz zu schaffen, verknüpfen das Bit mit OR und verschieben n anschließend nach rechts.
Nach 32 Iterationen enthält die Ausgabe-Ganzzahl alle 32 Bits von n in umgekehrter Reihenfolge. Das entspricht O(32) = O(1) pro Aufruf oder bei wiederholten Aufrufen auf 8-Bit-Blöcken mit Caching amortisiert O(1).
def reverse_bits(n):
result = 0
for _ in range(32):
result = (result << 1) | (n & 1) # shift result left, OR in rightmost bit
n >>= 1 # move to next bit
return result
# Test with known values
print(reverse_bits(0b00000010100101000001111010011100)) # 964176192
print(reverse_bits(0b11111111111111111111111111111101)) # 3221225471
print(reverse_bits(0)) # 0
print(reverse_bits(1)) # 2147483648 (bit 0 goes to bit 31)
print(reverse_bits(0b10000000000000000000000000000000)) # 1Bits umkehren: Teile-und-herrsche-Ansatz
Ein schnellerer Ansatz mit O(log 32) = O(1) kehrt Bits mithilfe eines Teile-und-herrsche-Austauschs um. Zuerst werden benachbarte Bits vertauscht, dann benachbarte 2-Bit-Gruppen, anschließend 4-Bit-Gruppen und so weiter. Jede Austauschebene verwendet Masken, um abwechselnde Gruppen zu trennen, und Verschiebungen, um sie ineinanderzuweben. Nach 5 Austauschen sind alle 32 Bits umgekehrt.
Dieser Ansatz verwendet unabhängig von der Eingabe eine konstante Anzahl fester Operationen und wird in Hardwareimplementierungen eingesetzt. Die Masken sind Konstanten: 0x55555555 (abwechselndes 01-Muster), 0x33333333 (abwechselndes 0011-Muster), 0x0f0f0f0f (abwechselndes 00001111-Muster) usw.
def reverse_bits_dc(n):
# Treat n as 32-bit unsigned
n &= 0xFFFFFFFF
# Swap adjacent bits
n = ((n & 0x55555555) << 1) | ((n >> 1) & 0x55555555)
# Swap adjacent 2-bit groups
n = ((n & 0x33333333) << 2) | ((n >> 2) & 0x33333333)
# Swap adjacent 4-bit groups
n = ((n & 0x0f0f0f0f) << 4) | ((n >> 4) & 0x0f0f0f0f)
# Swap adjacent bytes
n = ((n & 0x00ff00ff) << 8) | ((n >> 8) & 0x00ff00ff)
# Swap adjacent 16-bit halves
n = ((n & 0x0000ffff) << 16) | ((n >> 16) & 0x0000ffff)
return n & 0xFFFFFFFF
# Verify against iterative version
def reverse_bits_iter(n):
result = 0
for _ in range(32):
result = (result << 1) | (n & 1); n >>= 1
return result
for test in [0b10110100, 0b11111111, 0, 1, 0xDEADBEEF]:
assert reverse_bits_dc(test) == reverse_bits_iter(test)
print(f'{test:#010x} reversed: {reverse_bits_dc(test):#010x}')Anzahl der 1-Bits (Hamming-Gewicht)
Das Problem Number of 1 Bits (LeetCode 191) verlangt das Hamming-Gewicht (Popcount) einer vorzeichenlosen Ganzzahl. Es gibt drei Ansätze mit unterschiedlichen Eigenschaften: eine naive Schleife (O(32)), Brian Kernighans Methode (O(k), wobei k die Anzahl der gesetzten Bits ist) und Pythons eingebaute Funktion n.bit_count() (ab 3.10).
Die Methode von Brian Kernighan wird in Interviews bevorzugt, weil sie das Verständnis des Tricks n & (n-1) zeigt. Jede Iteration entfernt das niedrigste gesetzte Bit, sodass die Schleife genau so oft ausgeführt wird, wie 1-Bits vorhanden sind — bei dünn besetzten Ganzzahlen deutlich schneller als das vollständige Durchlaufen aller 32 Bits.
def hamming_weight_naive(n):
count = 0
while n:
count += n & 1
n >>= 1
return count
def hamming_weight_kernighan(n):
count = 0
while n:
n &= n - 1 # clear lowest set bit
count += 1
return count
# Python 3.10+
# def hamming_weight_builtin(n): return n.bit_count()
for n in [0, 1, 11, 128, 255, 0xDEADBEEF]:
naive = hamming_weight_naive(n)
kern = hamming_weight_kernighan(n)
bits = bin(n).count('1')
print(f'{n:#012b} ({n:10d}): naive={naive}, kern={kern}, bin={bits}')Summe aufeinanderfolgender Bits: Präfixansatz
Manchmal müssen Sie die Anzahl der 1-Bits in einem Bereich [l, r] schnell bestimmen. Erstellen Sie eine Präfixsumme der gesetzten Bits für 0 bis n: prefix[i] = prefix[i-1] + bin(i).count('1'). Die Anzahl im Bereich [l, r] ist dann prefix[r] - prefix[l-1]. Dadurch sind nach einer Vorverarbeitung mit O(n) Bereichsabfragen in O(1) möglich.
Dieses Verfahren lässt sich auf beliebige bitbasierte Aggregationen über einen Bereich verallgemeinern. Um beispielsweise Zahlen in [l, r] mit einer geraden Anzahl gesetzter Bits zu zählen, verwenden Sie dieselbe Präfixtechnik, aber mit einer anderen Akkumulationsfunktion.
def build_bit_prefix(n):
prefix = [0] * (n + 2)
for i in range(1, n + 1):
prefix[i] = prefix[i - 1] + bin(i).count('1')
return prefix
def count_bits_range(prefix, l, r):
return prefix[r] - prefix[l - 1]
# Build prefix for 0..15
prefix = build_bit_prefix(15)
print('Prefix sums (set bit counts up to i):')
for i in range(16):
print(f' i={i:2d} ({bin(i)[2:]:4s}): bits={bin(i).count("1")}, prefix={prefix[i]}')
# Range queries
print(f'\nSet bits in [5, 10]: {count_bits_range(prefix, 5, 10)}')
print(f'Set bits in [1, 15]: {count_bits_range(prefix, 1, 15)}')Bits negativer Zahlen umkehren
In Python sind Ganzzahlen vorzeichenbehaftet und haben eine beliebige Breite. Beim Umkehren von Bits für das LeetCode-Problem müssen wir die Eingabe als vorzeichenlose 32-Bit-Ganzzahl behandeln. Maskieren Sie die Eingabe vor der Verarbeitung mit & 0xFFFFFFFF, um sicherzustellen, dass nur 32 Bits berücksichtigt werden. Auch die Ausgabe sollte eine vorzeichenlose 32-Bit-Ganzzahl sein, also nicht negativ.
Wenn Sie eine Python-Ganzzahl erhalten, die möglicherweise negativ ist (im Sinne des Zweierkomplements), wenden Sie zunächst & 0xFFFFFFFF an, um die vorzeichenlose 32-Bit-Darstellung zu erhalten, und kehren Sie anschließend die Bits um. Das Ergebnis ist immer eine nicht negative Ganzzahl zwischen 0 und 2^32 - 1.
def reverse_bits_signed_safe(n):
n &= 0xFFFFFFFF # treat as 32-bit unsigned
result = 0
for _ in range(32):
result = (result << 1) | (n & 1)
n >>= 1
return result & 0xFFFFFFFF
# Python treats -1 as all 1s in two's complement
print(f'-1 as 32-bit unsigned: {-1 & 0xFFFFFFFF:#010x}') # 0xffffffff
print(f'Reversed: {reverse_bits_signed_safe(-1):#010x}') # 0xffffffff (all 1s reversed = all 1s)
# -2 in 32-bit = 0xFFFFFFFE = 11...10
print(f'-2 as 32-bit unsigned: {-2 & 0xFFFFFFFF:#010x}') # 0xfffffffe
print(f'Reversed: {reverse_bits_signed_safe(-2):#010x}') # 0x7fffffffBitmanipulations-DP: Muster beim Zählen von Bits
Das Problem des Bitzählens zeigt ein allgemeines Muster der Bit-DP: Wenn Sie die Lösung für eine kleinere Variante von i kennen, können Sie die Lösung für i mithilfe einer Bitoperation in konstanter Zeit berechnen. Dieses Muster lässt sich auf andere Probleme des Bitzählens übertragen, etwa auf das Zählen von Zahlen mit genau k gesetzten Bits in [0, n] (mithilfe einer Binäraufzählung) oder auf das Bestimmen der höchsten Zweierpotenz, durch die jede Zahl teilbar ist.
Eine weitere nützliche Beobachtung: Die Anzahl der gesetzten Bits von i folgt innerhalb jedes Zweierpotenzintervalls einem wiederkehrenden Muster. Das Muster für [2^k, 2^(k+1) - 1] entspricht dem Muster für [0, 2^k - 1], wobei jeder Wert um 1 erhöht ist, weil Bit k in diesem Bereich immer gesetzt ist.
# Visualise the repeating pattern
def show_bit_pattern(n):
bits = [bin(i).count('1') for i in range(n + 1)]
print('i | bits | pattern')
for i, b in enumerate(bits):
block = i.bit_length() - 1 if i > 0 else 0
print(f'{i:2d} ({bin(i)[2:]:4s}) | {b} | block {block}')
return bits
bits = show_bit_pattern(15)
# Verify the pattern: bits[i] = bits[i - highest_power] + 1 for i >= 2^k
print('\nVerify pattern:')
for i in range(1, 16):
highest_pow = 1 << (i.bit_length() - 1)
if highest_pow < i:
prev_i = i - highest_pow
print(f'bits[{i}] = bits[{prev_i}] + 1 = {bits[prev_i]} + 1 = {bits[i]}')Alle drei kombinieren: Eine integrierte Übung
Viele Interviewaufgaben kombinieren Bitzählung, die Logik für fehlende Zahlen und Bitumkehrung in einer einzigen Frage. Beispiel: Gegeben sei ein Array, dessen Elemente n-Bit-Ganzzahlen sind, wobei ein Element fehlt. Finden Sie den fehlenden Wert. Oder: Gegeben sei ein Datenstrom von Bitanzahlen. Rekonstruieren Sie die fehlende Ganzzahl. Dafür müssen Sie erkennen, welche Teiltechnik jeweils anzuwenden ist.
Üben Sie, eine mentale Landkarte aufzubauen: Wenn eine Aufgabe das Finden fehlender Elemente erwähnt, denken Sie an XOR oder eine Summe. Wenn es heißt, 1-Bits effizient zu zählen, denken Sie an Kernighan oder DP. Wenn es heißt, Bits umzukehren, denken Sie an einen iterativen Ansatz oder Teile und Herrsche. Dies sind die drei wichtigsten Werkzeuge der Bitmanipulation in Interviews.
# Integrated exercise: given bit-count array, find the missing number
# arr[i] = number of 1 bits in i, for all i in 0..n except one
# Reconstruct the missing number
def find_missing_from_bit_counts(bit_counts, n):
# Rebuild full count array
full = [bin(i).count('1') for i in range(n + 1)]
# Find which index is missing by comparing
for i, count in enumerate(bit_counts):
if full[i] != count:
return i - 1 # the entry before the mismatch is missing
return n # last element missing
# Simpler: use XOR on indices matching bit counts
# (This is simplified for illustration)
bits = [0,1,1,2,1,2,2,3,0,1] # bit counts for 0..9 with 8 missing
# Normal: [0,1,1,2,1,2,2,3,1,2]
# Missing is index 8
full = [bin(i).count('1') for i in range(10)]
missing_idx = None
for i in range(10):
if i >= len(bits) or bits[i] != full[i]:
missing_idx = i
break
print(f'Missing number: {missing_idx}')Caching für die Bitumkehrung
Bei wiederholten Aufrufen zur Bitumkehrung, etwa in einer Hardwaresimulation, können Sie die Ergebnisse für 8-Bit-Blöcke zwischenspeichern. Da jedes Byte nur 256 verschiedene Werte annehmen kann, berechnen Sie für jeden Wert von 0 bis 255 das umgekehrte Byte vorab. Um eine 32-Bit-Ganzzahl umzukehren, teilen Sie sie in vier 8-Bit-Blöcke auf, kehren jeden Block um und setzen sie in umgekehrter Reihenfolge wieder zusammen.
Dadurch reduziert sich jeder Aufruf auf vier Tabellenzugriffe und Bitoperationen — bei der Verarbeitung großer Datenmengen deutlich schneller als eine Schleife mit 32 Iterationen. Der Cache wird einmalig in O(256 × 8) Zeit aufgebaut und für alle folgenden Aufrufe in O(1) wiederverwendet.
# Build 8-bit reverse cache
def build_reverse_byte_cache():
cache = [0] * 256
for i in range(256):
n, result = i, 0
for _ in range(8):
result = (result << 1) | (n & 1)
n >>= 1
cache[i] = result
return cache
cache = build_reverse_byte_cache()
def reverse_bits_cached(n):
return (cache[n & 0xFF] << 24 |
cache[(n >> 8) & 0xFF] << 16 |
cache[(n >> 16) & 0xFF] << 8 |
cache[(n >> 24) & 0xFF])
# Test
for test in [0b10110100, 0b11111111, 0x12345678]:
cached = reverse_bits_cached(test)
# Reference: iterative
n, result = test, 0
for _ in range(32): result = (result << 1) | (n & 1); n >>= 1
assert cached == result
print(f'{test:#010x} => {cached:#010x}')Kurztest
Testen Sie Ihr Verständnis der Konzepte aus dieser Lektion aus Data Structures & Algorithms — Coding Interview Prep.
Zusammenfassung der Lektion
In dieser Lektion haben Sie gelernt: Bits werden mit DP gezählt, wobei dp[i] = dp[i >> 1] + (i & 1) oder dp[i] = dp[i & (i-1)] + 1 eine Laufzeit von O(n) ermöglicht; eine fehlende Zahl lässt sich in O(n)/O(1) bestimmen, indem alle Indizes mit allen Werten per XOR verknüpft werden oder die arithmetische Summenformel verwendet wird; und das Umkehren von 32 Bits erfolgt iterativ in O(32) oder mithilfe der Teile-und-herrsche-Technik mit Masken. Als Nächstes untersuchen wir monotone Stacks, beginnend mit der Invariante für aufsteigende und absteigende Reihenfolgen sowie Abfragen nach dem nächstgrößeren Element.
Häufig gestellte Fragen
Ist die Lektion „Bits zählen, fehlende Zahl und Bits umkehren“ kostenlos?
Ja — der vollständige Text von „Bits zählen, fehlende Zahl und Bits umkehren“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Bits zählen, fehlende Zahl und Bits umkehren“?
Berechnen Sie Bitanzahlen für 0..n mit DP und dem Trick des niedrigsten gesetzten Bits, finden Sie eine fehlende Zahl per XOR und kehren Sie die Bits einer 32-Bit-Ganzzahl um. Du übst Coding Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Coding Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. Coding Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 4 von 4.
Wie lange dauert die Lektion „Bits zählen, fehlende Zahl und Bits umkehren“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Coding Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede Coding Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Bitweise Operatoren: AND, OR, XOR, NOT und Verschiebungen
- Single Number und XOR-Eigenschaften
- Bitmasken: Setzen, Löschen, Umschalten und Prüfen
- Bits zählen, fehlende Zahl und Bits umkehren