Menghitung Bit, Angka yang Hilang, dan Membalik Bit
Hitung jumlah bit untuk 0..n menggunakan DP dan trik bit-terendah-aktif, temukan angka yang hilang melalui XOR, lalu balik bit bilangan bulat 32-bit
Menghitung Bit, Angka yang Hilang, dan Membalik Bit adalah pelajaran DSA Interview Prep gratis di CoddyKit. Ini adalah pelajaran 4 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar DSA Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus DSA Interview Prep mencakup 4 pelajaran total.
Gambaran Umum Persoalan Penghitungan Bit
Persoalan Penghitungan Bit (LeetCode 338) meminta: jika diberikan n, kembalikan larik ans berukuran n+1 dengan ans[i] sebagai jumlah bit 1 dalam i. Pendekatan naif memerlukan O(n log n) — hitung bit setiap bilangan secara terpisah. Pendekatan DP memerlukan O(n) dengan memanfaatkan hubungan antara i dan separuhnya atau bit yang disetel paling rendah.
Dua pengamatan utama mendasari DP: (1) i >> 1 menghapus bit paling rendah, sehingga bits[i] = bits[i >> 1] + (i & 1). (2) Menghapus bit yang disetel paling rendah: bits[i] = bits[i & (i-1)] + 1. Keduanya memberikan waktu O(n) dan ruang O(n) untuk larik keluaran.
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))Mengapa Rumus Rekurensi DP Berfungsi
Untuk rumus rekurensi pergeseran kanan dp[i] = dp[i >> 1] + (i & 1): pembagian dengan 2, yaitu pergeseran ke kanan, menghapus bit terakhir. Jika bit terakhir bernilai 1, jumlahnya bertambah 1; jika bernilai 0, tidak ada perubahan. Jadi bits[i] = bits[i // 2] + (i mod 2).
Untuk rumus rekurensi bit yang disetel paling rendah dp[i] = dp[i & (i-1)] + 1: i & (i-1) menghapus bit 1 paling kanan, sehingga memiliki satu bit yang disetel lebih sedikit daripada i. Oleh karena itu, jumlahnya adalah jumlah nilai yang telah dikurangi tersebut ditambah 1. Kedua rumus rekurensi memproses i dalam urutan menaik, sehingga subpersoalan yang lebih kecil selalu diselesaikan lebih dahulu.
# 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)Bilangan yang Hilang: Pendekatan XOR dan Jumlah
Persoalan Bilangan yang Hilang (LeetCode 268) memberikan larik berisi n bilangan berbeda dalam [0, n], dengan tepat satu bilangan yang hilang. Pendekatan XOR: lakukan XOR pada semua indeks 0..n dan semua nilai dalam larik. Pasangan yang sama saling membatalkan, sehingga tersisa bilangan yang hilang. Pendekatan jumlah: expected = n*(n+1)//2, lalu kembalikan expected - sum(nums).
Keduanya memerlukan waktu O(n) dan ruang O(1). Pendekatan XOR lebih tangguh dalam bahasa dengan bilangan bulat berlebar tetap karena menghindari kemungkinan luapan. Dalam Python, keduanya bekerja dengan baik karena bilangan bulat memiliki presisi tak terbatas.
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)}')Membalik Bit Bilangan Bulat 32-Bit
Persoalan Membalik Bit (LeetCode 190) meminta Anda membalik representasi biner bilangan bulat tak bertanda 32-bit. Pendekatan iteratif memproses masing-masing dari 32 bit, dari kanan ke kiri pada masukan, lalu menempatkannya dari kiri ke kanan pada keluaran. Pada setiap iterasi: ekstrak bit paling kanan dengan n & 1, geser keluaran ke kiri untuk menyediakan ruang, lakukan OR dengan bit tersebut, lalu geser n ke kanan.
Setelah 32 iterasi, bilangan bulat keluaran berisi semua 32 bit n dalam urutan terbalik. Ini memerlukan O(32) = O(1) per panggilan, atau O(1) yang diamortisasi dengan penembolokan untuk panggilan berulang pada potongan 8-bit.
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)) # 1Membalik Bit: Bagi dan Taklukkan
Pendekatan O(log 32) = O(1) yang lebih cepat membalik bit menggunakan pertukaran bagi dan taklukkan. Pertama, tukar bit yang bersebelahan, lalu tukar kelompok 2-bit yang bersebelahan, kemudian kelompok 4-bit, dan seterusnya. Setiap tingkat pertukaran menggunakan masker untuk memisahkan kelompok berselang-seling dan pergeseran untuk menyisipkannya. Setelah 5 pertukaran, semua 32 bit telah dibalik.
Pendekatan ini menggunakan O(1) operasi tetap, apa pun masukannya, dan digunakan dalam implementasi perangkat keras. Maskernya adalah konstanta: 0x55555555 (pola 01 berselang-seling), 0x33333333 (pola 0011 berselang-seling), 0x0f0f0f0f (pola 00001111 berselang-seling), dan seterusnya.
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}')Jumlah Bit 1 (Bobot Hamming)
Persoalan Jumlah Bit 1 (LeetCode 191) meminta bobot Hamming, atau jumlah bit 1, dari sebuah bilangan bulat tak bertanda. Tiga pendekatan dengan kompromi berbeda: perulangan naif (O(32)), Brian Kernighan (O(k), dengan k = bit yang disetel), dan n.bit_count() bawaan Python (3.10+).
Metode Brian Kernighan lebih disukai dalam wawancara karena menunjukkan pemahaman terhadap trik n & (n-1). Setiap iterasi menghapus bit yang disetel paling rendah, sehingga perulangan berjalan tepat sebanyak jumlah bit 1 — jauh lebih cepat daripada pemindaian penuh 32-bit untuk bilangan bulat yang jarang memiliki bit 1.
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}')Jumlah Bit Berurutan: Pendekatan Prefiks
Terkadang Anda perlu menghitung bit 1 dalam rentang [l, r] dengan cepat. Buat jumlah prefiks bit yang disetel untuk 0..n: prefix[i] = prefix[i-1] + bin(i).count('1'). Kemudian jumlah untuk rentang [l, r] adalah prefix[r] - prefix[l-1]. Dengan demikian, kueri rentang dapat dilakukan dalam O(1) setelah prapemrosesan O(n).
Teknik ini dapat diterapkan secara umum pada agregat berbasis bit apa pun dalam suatu rentang. Sebagai contoh, untuk menghitung bilangan dalam [l, r] yang memiliki jumlah bit yang disetel genap, gunakan teknik prefiks yang sama dengan fungsi akumulasi berbeda.
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)}')Membalik Bit untuk Bilangan Negatif
Dalam Python, bilangan bulat bertanda dan memiliki lebar yang tidak terbatas. Saat membalik bit untuk persoalan LeetCode, kita harus memperlakukan masukan sebagai bilangan bulat tak bertanda 32-bit. Masker masukan dengan & 0xFFFFFFFF sebelum memprosesnya untuk memastikan hanya 32 bit yang dipertimbangkan. Keluaran juga harus berupa bilangan bulat tak bertanda 32-bit, yaitu bilangan non-negatif.
Jika Anda mendapatkan bilangan bulat Python yang mungkin negatif, dalam pengertian komplemen dua, terlebih dahulu terapkan & 0xFFFFFFFF untuk memperoleh representasi tak bertanda 32-bit, lalu balikkan. Hasilnya selalu berupa bilangan bulat non-negatif antara 0 dan 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 Manipulasi Bit: Menghitung Pola Bit
Persoalan penghitungan bit mengungkap pola umum untuk DP bit: jika Anda mengetahui jawaban untuk versi i yang lebih kecil, Anda dapat menghitung jawaban untuk i menggunakan operasi bit berwaktu konstan. Pola ini dapat diterapkan secara umum pada persoalan penghitungan bit lainnya, seperti menghitung bilangan dengan tepat k bit yang disetel dalam [0, n] menggunakan enumerasi biner, atau menentukan pangkat dua tertinggi yang membagi setiap bilangan.
Pengamatan lain yang berguna: jumlah bit yang disetel untuk i mengikuti pola berulang dalam setiap interval pangkat dua. Pola untuk [2^k, 2^(k+1) - 1] sama dengan pola untuk [0, 2^k - 1], dengan setiap nilai ditambah 1, karena bit k selalu disetel dalam rentang ini.
# 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]}')Menggabungkan Ketiganya: Latihan Terpadu
Banyak persoalan wawancara menggabungkan penghitungan bit, logika bilangan yang hilang, dan pembalikan bit dalam satu pertanyaan. Contohnya: diberikan larik yang elemennya merupakan bilangan bulat n-bit dan satu elemen hilang, temukan nilai yang hilang. Atau: diberikan aliran jumlah bit, rekonstruksi bilangan bulat yang hilang. Semua ini memerlukan pengenalan teknik bagian mana yang berlaku.
Latihlah membuat peta mental: jika persoalan menyebutkan pencarian elemen yang hilang, pikirkan XOR atau jumlah. Jika menyatakan 'hitung bit 1 secara efisien', pikirkan Kernighan atau DP. Jika menyatakan 'balik bit', pikirkan pendekatan iteratif atau bagi dan taklukkan. Inilah tiga alat inti manipulasi bit dalam wawancara.
# 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}')Penembolokan Bit untuk Pembalikan Bit
Untuk panggilan berulang dalam pembalikan bit, misalnya dalam simulasi perangkat keras, tembolok hasil untuk potongan 8-bit. Karena setiap bita hanya dapat memiliki 256 nilai, hitung terlebih dahulu bita terbalik untuk setiap nilai 0-255. Untuk membalik bilangan bulat 32-bit, pecah menjadi empat potongan 8-bit, balikkan masing-masing, lalu rakit kembali dalam urutan terbalik.
Hal ini mengurangi setiap panggilan menjadi empat pencarian tabel dan operasi bit — jauh lebih cepat daripada perulangan 32 iterasi untuk pemrosesan massal. Tembolok dibuat sekali dalam waktu O(256 × 8) dan digunakan kembali untuk semua panggilan berikutnya dalam 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}')Pemeriksaan Cepat
Ujilah pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.
Rangkuman Pelajaran
Dalam pelajaran ini Anda telah mempelajari: penghitungan bit menggunakan DP dengan dp[i] = dp[i >> 1] + (i & 1) atau dp[i] = dp[i & (i-1)] + 1 untuk waktu O(n), bilangan yang hilang dapat diselesaikan dalam O(n)/O(1) dengan melakukan XOR pada semua indeks dan semua nilai atau menggunakan rumus jumlah aritmetika, dan pembalikan 32 bit dilakukan secara iteratif dalam O(32) atau dengan teknik masker bagi dan taklukkan. Berikutnya kita akan mempelajari tumpukan monoton, dimulai dari invarian menaik versus menurun dan kueri elemen lebih besar berikutnya.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Menghitung Bit, Angka yang Hilang, dan Membalik Bit” gratis?
Ya — teks lengkap “Menghitung Bit, Angka yang Hilang, dan Membalik Bit” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus DSA Interview Prep, upgrade ke CoddyKit PRO. Kursus DSA Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Menghitung Bit, Angka yang Hilang, dan Membalik Bit”?
Hitung jumlah bit untuk 0..n menggunakan DP dan trik bit-terendah-aktif, temukan angka yang hilang melalui XOR, lalu balik bit bilangan bulat 32-bit Kamu berlatih DSA Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai DSA Interview Prep?
Tidak diperlukan pengalaman sebelumnya. DSA Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 4 dari 4.
Berapa lama pelajaran “Menghitung Bit, Angka yang Hilang, dan Membalik Bit” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran DSA Interview Prep ini?
Ya. Setiap pelajaran DSA Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Operator Bitwise: AND, OR, XOR, NOT, Pergeseran
- Single Number dan Sifat XOR
- Masker Bit: Set, Clear, Toggle, Check
- Menghitung Bit, Angka yang Hilang, dan Membalik Bit