Zliczanie bitów, brakująca liczba i odwracanie bitów
Obliczać liczbę bitów dla wartości od 0 do n za pomocą DP i sztuczki z najmłodszym ustawionym bitem, znajdować brakującą liczbę przez XOR oraz odwracać bity liczby całkowitej 32-bitowej
Zliczanie bitów, brakująca liczba i odwracanie bitów to bezpłatna lekcja DSA Interview Prep na CoddyKit. To lekcja 4 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej DSA Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Omówienie problemu Counting Bits
Problem Counting Bits (LeetCode 338) polega na tym, że dla danej wartości n należy zwrócić tablicę ans rozmiaru n+1, w której ans[i] oznacza liczbę bitów równych 1 w i. Naiwne podejście ma złożoność O(n log n), ponieważ bity trzeba zliczyć osobno dla każdej liczby. Podejście DP działa w czasie O(n), wykorzystując zależność między i a jego połową lub najmłodszym ustawionym bitem.
DP opiera się na dwóch kluczowych obserwacjach: (1) i >> 1 usuwa najmłodszy bit, więc bits[i] = bits[i >> 1] + (i & 1). (2) Wyczyszczenie najmłodszego ustawionego bitu daje: bits[i] = bits[i & (i-1)] + 1. Obie metody mają złożoność czasową O(n) i pamięciową O(n) ze względu na tablicę wynikową.
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))Dlaczego rekurencje DP działają
W przypadku rekurencji z przesunięciem w prawo dp[i] = dp[i >> 1] + (i & 1) dzielenie przez 2, czyli przesunięcie w prawo, usuwa ostatni bit. Jeśli ostatnim bitem było 1, licznik zwiększa się o 1, a jeśli 0 — pozostaje bez zmian. Zatem bits[i] = bits[i // 2] + (i mod 2).
W przypadku rekurencji z najmłodszym ustawionym bitem dp[i] = dp[i & (i-1)] + 1 wyrażenie i & (i-1) czyści skrajny prawy bit równy 1, więc wynik ma o jeden ustawiony bit mniej niż i. Liczba bitów dla i jest zatem równa liczbie bitów tej zmniejszonej wartości powiększonej o 1. Obie rekurencje przetwarzają i w kolejności rosnącej, dlatego mniejsze podproblemy są zawsze rozwiązywane wcześniej.
# 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)Missing Number: podejścia z XOR i sumą
Problem Missing Number (LeetCode 268) polega na otrzymaniu tablicy n różnych liczb z zakresu [0, n], w której brakuje dokładnie jednej liczby. Podejście z XOR: należy wykonać XOR na wszystkich indeksach od 0 do n oraz na wszystkich wartościach w tablicy. Pary redukują się, pozostawiając brakującą liczbę. Podejście z sumą: expected = n*(n+1)//2, a następnie należy zwrócić expected - sum(nums).
Oba podejścia mają złożoność czasową O(n) i pamięciową O(1). Podejście z XOR jest bardziej odporne w językach używających liczb całkowitych o stałej szerokości, ponieważ pozwala uniknąć potencjalnego przepełnienia. W Pythonie oba podejścia działają poprawnie, ponieważ liczby całkowite mają dowolną precyzję.
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)}')Odwracanie bitów 32-bitowej liczby całkowitej
Problem Reverse Bits (LeetCode 190) wymaga odwrócenia reprezentacji binarnej 32-bitowej liczby całkowitej bez znaku. Podejście iteracyjne polega na przetworzeniu każdego z 32 bitów wejścia od prawej do lewej i umieszczeniu ich w wyniku od lewej do prawej. W każdej iteracji należy wyodrębnić skrajny prawy bit za pomocą n & 1, przesunąć wynik w lewo, aby zrobić miejsce, wstawić bit operacją OR, a następnie przesunąć n w prawo.
Po 32 iteracjach wynik zawiera wszystkie 32 bity n w odwrotnej kolejności. Daje to O(32) = O(1) na wywołanie lub zamortyzowane O(1) przy użyciu buforowania dla powtarzających się wywołań na fragmentach 8-bitowych.
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)) # 1Reverse Bits: metoda dziel i zwyciężaj
Szybsze podejście O(log 32) = O(1) odwraca bity za pomocą zamiany metodą dziel i zwyciężaj. Najpierw zamienia się sąsiednie bity, następnie sąsiednie grupy 2-bitowe, potem grupy 4-bitowe i tak dalej. Na każdym poziomie zamiany maski oddzielają naprzemienne grupy, a przesunięcia przeplatają je ze sobą. Po 5 zamianach wszystkie 32 bity są odwrócone.
To podejście używa stałej liczby operacji niezależnie od danych wejściowych i jest stosowane w implementacjach sprzętowych. Maski są stałymi: 0x55555555 (naprzemienny wzorzec 01), 0x33333333 (naprzemienny wzorzec 0011), 0x0f0f0f0f (naprzemienny wzorzec 00001111) itd.
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}')Number of 1 Bits (waga Hamminga)
Problem Number of 1 Bits (LeetCode 191) wymaga obliczenia wagi Hamminga (popcount) liczby całkowitej bez znaku. Istnieją trzy podejścia o różnych kompromisach: naiwna pętla (O(32)), metoda Briana Kernighana (O(k), gdzie k oznacza liczbę ustawionych bitów) oraz wbudowana metoda Pythona n.bit_count() (3.10+).
Metoda Briana Kernighana jest preferowana podczas rozmów rekrutacyjnych, ponieważ pokazuje zrozumienie sztuczki n & (n-1). Każda iteracja usuwa najmłodszy ustawiony bit, więc pętla wykonuje się dokładnie tyle razy, ile jest bitów równych 1 — dla liczb z niewielką liczbą ustawionych bitów jest to znacznie szybsze niż pełne skanowanie 32 bitów.
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}')Zliczanie kolejnych bitów: podejście z sumami prefiksowymi
Czasami trzeba szybko zliczyć bity równe 1 w zakresie [l, r]. Należy zbudować sumę prefiksową ustawionych bitów dla zakresu od 0 do n: prefix[i] = prefix[i-1] + bin(i).count('1'). Następnie liczba bitów w zakresie [l, r] wynosi prefix[r] - prefix[l-1]. Po wstępnym przetwarzaniu w czasie O(n) pozwala to wykonywać zapytania o zakres w czasie O(1).
Można to uogólnić na dowolne agregaty oparte na bitach obliczane dla zakresu. Na przykład zliczanie liczb w [l, r] z parzystą liczbą ustawionych bitów wykorzystuje tę samą technikę sum prefiksowych, ale inną funkcję akumulacji.
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)}')Odwracanie bitów liczb ujemnych
W Pythonie liczby całkowite są ze znakiem i mają dowolną szerokość. Podczas odwracania bitów na potrzeby problemu z LeetCode należy traktować dane wejściowe jako 32-bitową liczbę całkowitą bez znaku. Przed przetwarzaniem trzeba zamaskować dane wejściowe za pomocą & 0xFFFFFFFF, aby uwzględnić tylko 32 bity. Wynik również powinien być 32-bitową liczbą całkowitą bez znaku, czyli nieujemną.
Jeśli otrzymają Państwo liczbę całkowitą Pythona, która może być ujemna (w sensie reprezentacji w kodzie uzupełnień do dwóch), należy najpierw zastosować & 0xFFFFFFFF, aby uzyskać reprezentację 32-bitową bez znaku, a następnie odwrócić bity. Wynik zawsze jest nieujemną liczbą całkowitą z zakresu od 0 do 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 z operacjami bitowymi: wzorce zliczania bitów
Problem zliczania bitów ujawnia ogólny wzorzec DP bitowego: jeśli znają Państwo wynik dla mniejszej wersji i, mogą go Państwo obliczyć dla i za pomocą stałoczasowej operacji bitowej. Wzorzec ten można uogólnić na inne problemy związane ze zliczaniem bitów, takie jak zliczanie liczb z dokładnie k ustawionymi bitami w [0, n] (za pomocą enumeracji binarnej) lub znajdowanie najwyższej potęgi dwójki dzielącej każdą liczbę.
Inna przydatna obserwacja: liczba ustawionych bitów dla i powtarza się w każdym przedziale wyznaczonym przez kolejne potęgi dwójki. Wzorzec dla [2^k, 2^(k+1) - 1] jest taki sam jak dla [0, 2^k - 1], ale każda wartość zostaje zwiększona o 1, ponieważ bit k jest zawsze ustawiony w tym zakresie.
# 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]}')Połączenie wszystkich trzech: ćwiczenie integrujące
Wiele zadań rekrutacyjnych łączy zliczanie bitów, logikę znajdowania brakującej liczby i odwracanie bitów w jednym problemie. Na przykład: dana jest tablica, której elementy są n-bitowymi liczbami całkowitymi, a jednej z nich brakuje — należy znaleźć brakującą wartość. Innym przykładem jest strumień liczności bitów, na podstawie którego trzeba odtworzyć brakującą liczbę całkowitą. Takie zadania wymagają rozpoznania, która podtechnika ma zastosowanie.
Warto wypracować sobie schemat rozumowania: jeśli zadanie dotyczy znajdowania brakujących elementów, należy pomyśleć o XOR lub sumie. Jeśli mówi o efektywnym zliczaniu jedynek, należy pomyśleć o metodzie Kernighana lub DP. Jeśli dotyczy odwracania bitów, należy rozważyć podejście iteracyjne albo dziel i zwyciężaj. Są to trzy podstawowe narzędzia manipulowania bitami podczas rozmów rekrutacyjnych.
# 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}')Buforowanie bitów na potrzeby Reverse Bits
W przypadku wielokrotnych wywołań odwracania bitów, na przykład w symulacji sprzętu, warto buforować wyniki dla fragmentów 8-bitowych. Każdy bajt może przyjmować tylko 256 wartości, więc należy wstępnie obliczyć odwrócony bajt dla każdej wartości od 0 do 255. Aby odwrócić 32-bitową liczbę całkowitą, trzeba podzielić ją na cztery fragmenty 8-bitowe, odwrócić każdy z nich, a następnie złożyć je w odwrotnej kolejności.
Zmniejsza to koszt każdego wywołania do czterech odwołań do tablicy i operacji bitowych — jest to znacznie szybsze niż pętla wykonująca 32 iteracje podczas przetwarzania dużych ilości danych. Bufor jest tworzony raz w czasie O(256 × 8), a następnie używany ponownie przy wszystkich kolejnych wywołaniach w czasie 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}')Szybki test
Sprawdź swoją znajomość zagadnień Data Structures & Algorithms — Coding Interview Prep z tej lekcji.
Podsumowanie lekcji
W tej lekcji nauczyli się Państwo, że: zliczanie bitów wykorzystuje DP z dp[i] = dp[i >> 1] + (i & 1) lub dp[i] = dp[i & (i-1)] + 1, osiągając czas O(n), brakującą liczbę można znaleźć w czasie O(n) i przy użyciu pamięci O(1), wykonując XOR na wszystkich indeksach i wszystkich wartościach albo stosując wzór na sumę arytmetyczną, a odwracanie 32 bitów wykonuje się iteracyjnie w czasie O(32) lub za pomocą techniki masek dziel i zwyciężaj. W następnej części zajmiemy się stosami monotonicznymi, zaczynając od niezmiennika rosnącego i malejącego oraz zapytań o następny większy element.
Często zadawane pytania
Czy lekcja „Zliczanie bitów, brakująca liczba i odwracanie bitów” jest bezpłatna?
Tak — pełny tekst „Zliczanie bitów, brakująca liczba i odwracanie bitów” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu DSA Interview Prep, przejdź na CoddyKit PRO. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Zliczanie bitów, brakująca liczba i odwracanie bitów”?
Obliczać liczbę bitów dla wartości od 0 do n za pomocą DP i sztuczki z najmłodszym ustawionym bitem, znajdować brakującą liczbę przez XOR oraz odwracać bity liczby całkowitej 32-bitowej Ćwiczysz DSA Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć DSA Interview Prep?
Nie wymagamy żadnego doświadczenia. DSA Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 4 z 4.
Ile czasu zajmuje lekcja „Zliczanie bitów, brakująca liczba i odwracanie bitów”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji DSA Interview Prep?
Tak. Każda lekcja DSA Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Operatory bitowe: AND, OR, XOR, NOT i przesunięcia
- Single Number i właściwości XOR
- Maski bitowe: ustawianie, zerowanie, przełączanie i sprawdzanie
- Zliczanie bitów, brakująca liczba i odwracanie bitów