Bits tellen, ontbrekend getal en bits omkeren
Bereken bitcounts voor 0..n met DP en de lowest-set-bit-truc, vind een ontbrekend getal met XOR en keer de bits van een 32-bits integer om.
Bits tellen, ontbrekend getal en bits omkeren is een gratis Voorbereiding op programmeerinterviews-les op CoddyKit. Dit is les 4 van 4. Je kunt de volledige les hieronder gratis lezen en daarna in de browser praktisch oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject Voorbereiding op programmeerinterviews. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Overzicht van het probleem Bits tellen
Het probleem Bits tellen (LeetCode 338) vraagt: geef, voor een gegeven n, een array ans van grootte n+1 terug waarin ans[i] het aantal 1-bits in i is. De naïeve aanpak heeft tijdcomplexiteit O(n log n): tel de bits van elk getal afzonderlijk. De DP-aanpak heeft tijdcomplexiteit O(n) door gebruik te maken van de relatie tussen i en zijn helft of zijn laagst ingestelde bit.
Twee belangrijke observaties vormen de basis van DP: (1) i >> 1 verwijdert de laagste bit, dus bits[i] = bits[i >> 1] + (i & 1). (2) De laagst ingestelde bit wissen: bits[i] = bits[i & (i-1)] + 1. Beide leveren tijdcomplexiteit O(n) en ruimtecomplexiteit O(n) op (voor de uitvoerarray).
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))Waarom de DP-recursieformules werken
Voor de recursieformule met rechtsverschuiving dp[i] = dp[i >> 1] + (i & 1): delen door 2 (naar rechts verschuiven) verwijdert de laatste bit. Als de laatste bit 1 was, neemt de telling met 1 toe; bij 0 verandert er niets. Dus bits[i] = bits[i // 2] + (i mod 2).
Voor de recursieformule met de laagst ingestelde bit dp[i] = dp[i & (i-1)] + 1: i & (i-1) wist de meest rechtse 1-bit, zodat deze waarde één ingestelde bit minder heeft dan i. De telling is daarom de telling van die gereduceerde waarde plus 1. Beide recursieformules verwerken i in oplopende volgorde, zodat kleinere deelproblemen altijd eerst worden opgelost.
# 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)Ontbrekend getal: XOR- en somaanpak
Het probleem Ontbrekend getal (LeetCode 268) geeft een array met n verschillende getallen in [0, n], waarvan er precies één ontbreekt. De XOR-aanpak: pas XOR toe op alle indices van 0 tot en met n en op alle waarden in de array. Paren heffen elkaar op, zodat het ontbrekende getal overblijft. De somaanpak: expected = n*(n+1)//2; geef expected - sum(nums) terug.
Beide hebben tijdcomplexiteit O(n) en ruimtecomplexiteit O(1). De XOR-aanpak is robuuster in talen met gehele getallen met een vaste bitbreedte, omdat mogelijke overloop wordt vermeden. In Python werken beide goed, omdat gehele getallen een willekeurige precisie hebben.
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 van een 32-bits geheel getal omkeren
Het probleem Bits omkeren (LeetCode 190) vraagt je om de binaire representatie van een 32-bits geheel getal zonder teken om te keren. De iteratieve aanpak: verwerk elk van de 32 bits van de invoer van rechts naar links en plaats ze van links naar rechts in de uitvoer. Haal bij elke iteratie de meest rechtse bit op met n & 1, verschuif de uitvoer naar links om ruimte te maken, voeg de bit toe met OR en verschuif n daarna naar rechts.
Na 32 iteraties bevat het uitvoergehele getal alle 32 bits van n in omgekeerde volgorde. Dit is O(32) = O(1) per aanroep, of O(1) geamortiseerd dankzij caching bij herhaalde aanroepen met blokken van 8 bits.
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 omkeren: verdelen en heersen
Een snellere aanpak met O(log 32) = O(1) keert bits om met wisselingen volgens het principe van verdelen en heersen. Eerst verwissel je aangrenzende bits, daarna aangrenzende groepen van 2 bits, vervolgens groepen van 4 bits, enzovoort. Elk wisselniveau gebruikt maskers om afwisselende groepen te scheiden en verschuivingen om ze te verweven. Na 5 wisselingen zijn alle 32 bits omgekeerd.
Deze aanpak gebruikt O(1) vaste bewerkingen, ongeacht de invoer, en wordt gebruikt in hardware-implementaties. De maskers zijn constanten: 0x55555555 (afwisselend 01-patroon), 0x33333333 (afwisselend 0011), 0x0f0f0f0f (afwisselend 00001111), enzovoort.
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}')Aantal 1-bits (Hamminggewicht)
Het probleem Aantal 1-bits (LeetCode 191) vraagt om het Hamminggewicht, oftewel het aantal 1-bits, van een geheel getal zonder teken. Er zijn drie aanpakken met verschillende afwegingen: een naïeve lus (O(32)), Brian Kernighan (O(k), waarbij k het aantal ingestelde bits is) en de ingebouwde functie n.bit_count() van Python (3.10+).
De methode van Brian Kernighan heeft de voorkeur tijdens sollicitatiegesprekken, omdat deze laat zien dat je de truc n & (n-1) begrijpt. Elke iteratie verwijdert de laagst ingestelde bit, zodat de lus precies zo vaak wordt uitgevoerd als er 1-bits zijn — veel sneller dan een volledige scan van 32 bits voor ijle gehele getallen.
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}')Som van opeenvolgende bits: aanpak met prefixsom
Soms moet je snel het aantal 1-bits in een bereik [l, r] tellen. Bouw een prefixsom van ingestelde bits voor 0..n: prefix[i] = prefix[i-1] + bin(i).count('1'). Vervolgens is de telling voor het bereik [l, r] prefix[r] - prefix[l-1]. Zo kun je na O(n) voorbewerking bereiken in O(1) opvragen.
Dit generaliseert naar elke bitgebaseerde aggregatie over een bereik. Zo kun je bijvoorbeeld getallen in [l, r] met een even aantal ingestelde bits tellen met dezelfde prefixtechniek, maar met een andere accumulatiefunctie.
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 omkeren voor negatieve getallen
In Python hebben gehele getallen een teken en een willekeurige bitbreedte. Bij het omkeren van bits voor het LeetCode-probleem moeten we de invoer behandelen als een 32-bits geheel getal zonder teken. Pas vóór de verwerking het masker & 0xFFFFFFFF toe op de invoer, zodat alleen 32 bits worden beschouwd. De uitvoer moet ook een 32-bits geheel getal zonder teken zijn, dus niet-negatief.
Als je een Python-geheel getal krijgt dat negatief kan zijn, in de zin van tweekomplementnotatie, pas je eerst & 0xFFFFFFFF toe om de representatie als 32-bits geheel getal zonder teken te krijgen en keer je de bits daarna om. Het resultaat is altijd een niet-negatief geheel getal tussen 0 en 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}') # 0x7fffffffDP met bitbewerkingen: patronen bij het tellen van bits
Het probleem Bits tellen laat een algemeen patroon voor bit-DP zien: als je het antwoord voor een kleinere variant van i kent, kun je het antwoord voor i berekenen met een bitbewerking in constante tijd. Dit generaliseert naar andere problemen rond het tellen van bits, zoals het tellen van getallen met precies k ingestelde bits in [0, n] (gebruik binaire opsomming) of het bepalen van de hoogste macht van twee waardoor elk getal deelbaar is.
Een andere nuttige observatie: het aantal ingestelde bits voor i volgt binnen elk interval van machten van twee een zich herhalend patroon. Het patroon voor [2^k, 2^(k+1) - 1] is hetzelfde als dat voor [0, 2^k - 1], waarbij elke waarde met 1 is verhoogd, omdat bit k in dit hele bereik ingesteld is.
# 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 drie combineren: een geïntegreerde oefening
Veel opgaven tijdens sollicitatiegesprekken combineren het tellen van bits, logica voor ontbrekende getallen en het omkeren van bits in één vraag. Bijvoorbeeld: gegeven een array waarvan de elementen gehele getallen van n bits zijn en waarvan er één ontbreekt, vind je de ontbrekende waarde. Of: gegeven een stroom met bittellingen reconstrueer je het ontbrekende gehele getal. Hiervoor moet je herkennen welke deeltechniek van toepassing is.
Oefen met het opbouwen van een mentaal overzicht: als een opgave spreekt over het vinden van ontbrekende elementen, denk dan aan XOR of een som. Als er staat 'tel 1-bits efficiënt', denk dan aan Kernighan of DP. Als er staat 'keer bits om', denk dan aan de iteratieve aanpak of verdelen en heersen. Dit zijn de drie belangrijkste hulpmiddelen voor bitbewerkingen tijdens sollicitatiegesprekken.
# 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}')Bits cachen voor het omkeren van bits
Bij herhaalde aanroepen om bits om te keren, bijvoorbeeld in een hardwaresimulatie, kun je resultaten voor blokken van 8 bits in een cache opslaan. Omdat elke byte slechts 256 waarden kan hebben, bereken je vooraf de omgekeerde byte voor elke waarde van 0 tot en met 255. Om een geheel getal van 32 bits om te keren, splits je het op in vier blokken van 8 bits, keer je elk blok om en stel je ze in omgekeerde volgorde weer samen.
Hierdoor bestaat elke aanroep uit vier opzoekingen in een tabel en bitbewerkingen — veel sneller dan een lus van 32 iteraties bij bulkverwerking. De cache wordt één keer opgebouwd in O(256 × 8) tijd en vervolgens voor alle volgende aanroepen hergebruikt in O(1).
# 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}')Korte controle
Test je begrip van de concepten uit Data Structures & Algorithms — Coding Interview Prep in deze les.
Samenvatting van de les
In deze les heb je geleerd dat bits tellen DP gebruikt met dp[i] = dp[i >> 1] + (i & 1) of dp[i] = dp[i & (i-1)] + 1 voor tijdcomplexiteit O(n), dat het ontbrekende getal in O(n)/O(1) wordt gevonden door alle indices met alle waarden te XOR'en of de rekenkundige somformule te gebruiken, en dat je 32 bits iteratief in O(32) kunt omkeren of de maskertechniek van verdelen en heersen kunt gebruiken. Hierna bekijken we monotone stacks, te beginnen met de oplopende versus aflopende invariant en opvragingen van eerstvolgend grotere elementen.
Leer Voorbereiding op programmeerinterviews met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 90
- Lessen
- 360
Veelgestelde vragen
Is de les “Bits tellen, ontbrekend getal en bits omkeren” gratis?
Ja — de volledige tekst van “Bits tellen, ontbrekend getal en bits omkeren” kun je hier gratis op het web lezen. Als je interactief wilt oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is, en de rest van de cursus Voorbereiding op programmeerinterviews wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Wat leer ik in “Bits tellen, ontbrekend getal en bits omkeren”?
Bereken bitcounts voor 0..n met DP en de lowest-set-bit-truc, vind een ontbrekend getal met XOR en keer de bits van een 32-bits integer om. Je oefent met Voorbereiding op programmeerinterviews door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met Voorbereiding op programmeerinterviews te beginnen?
Ervaring vooraf is niet nodig. Voorbereiding op programmeerinterviews op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 4 van 4.
Hoe lang duurt de les “Bits tellen, ontbrekend getal en bits omkeren”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over Voorbereiding op programmeerinterviews?
Ja. Elke les over Voorbereiding op programmeerinterviews bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- Bitwise-operatoren: AND, OR, XOR, NOT en shifts
- Single Number en XOR-eigenschappen
- Bitmaskers: instellen, wissen, omschakelen en controleren
- Bits tellen, ontbrekend getal en bits omkeren