Mengira Bit, Nombor Hilang dan Menterbalikkan Bit
Kira bilangan bit bagi 0..n menggunakan DP dan helah bit-set terendah, cari nombor yang hilang melalui XOR, dan terbalikkan bit integer 32-bit.
Mengira Bit, Nombor Hilang dan Menterbalikkan Bit ialah pelajaran Persediaan Temu Duga Pengaturcaraan percuma di CoddyKit. Ini ialah pelajaran 4 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran Persediaan Temu Duga Pengaturcaraan, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Gambaran Keseluruhan Masalah Pengiraan Bit
Masalah Pengiraan Bit (LeetCode 338) meminta: diberikan n, kembalikan tatasusunan ans bersaiz n+1, dengan ans[i] ialah bilangan bit 1 dalam i. Pendekatan naif mengambil masa O(n log n) — mengira bit dalam setiap nombor secara berasingan. Pendekatan DP mengambil masa O(n) dengan memanfaatkan hubungan antara i dengan separuhnya atau bit 1 terendahnya.
Dua pemerhatian utama menjadi asas DP: (1) i >> 1 membuang bit terendah, jadi bits[i] = bits[i >> 1] + (i & 1). (2) Mengosongkan bit 1 terendah: bits[i] = bits[i & (i-1)] + 1. Kedua-duanya memberikan masa O(n) dan ruang O(n) untuk tatasusunan output.
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))Sebab Hubungan Rekursi DP Berfungsi
Untuk the hubungan rekursi anjakan kanan dp[i] = dp[i >> 1] + (i & 1): pembahagian dengan 2, iaitu anjakan ke kanan, membuang bit terakhir. Jika bit terakhir ialah 1, kiraan bertambah 1; jika 0, tiada perubahan. Jadi bits[i] = bits[i // 2] + (i mod 2).
Untuk the hubungan rekursi bit 1 terendah dp[i] = dp[i & (i-1)] + 1: i & (i-1) mengosongkan bit 1 paling kanan, maka nilainya mempunyai satu bit yang ditetapkan kurang daripada i. Oleh itu, kiraan ialah kiraan the nilai yang dikurangkan itu ditambah 1. Kedua-dua hubungan rekursi memproses i dalam tertib menaik supaya submasalah yang lebih kecil sentiasa diselesaikan terlebih 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)Nombor Hilang: Pendekatan XOR dan Jumlah
Masalah Nombor Hilang (LeetCode 268) memberikan tatasusunan yang mengandungi n nombor berbeza dalam [0, n], dengan tepat satu nombor hilang. Pendekatan XOR: lakukan XOR pada semua indeks 0..n bersama-sama semua nilai dalam tatasusunan. Pasangan yang sama akan terbatal, lalu meninggalkan nombor yang hilang. Pendekatan jumlah: expected = n*(n+1)//2, kemudian kembalikan expected - sum(nums).
Kedua-duanya mengambil masa O(n) dan ruang O(1). Pendekatan XOR lebih teguh dalam bahasa yang menggunakan integer lebar tetap kerana ia mengelakkan kemungkinan limpahan. Dalam Python, kedua-duanya berfungsi dengan baik kerana integer mempunyai ketepatan arbitrari.
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)}')Pembalikan Bit bagi Integer 32 Bit
Masalah Pembalikan Bit (LeetCode 190) meminta anda membalikkan perwakilan binari integer tanpa tanda 32 bit. Pendekatan lelaran: proses setiap daripada 32 bit dari kanan ke kiri dalam input, lalu meletakkannya dari kiri ke kanan dalam output. Pada setiap lelaran: ekstrak bit paling kanan dengan n & 1, anjak output ke kiri untuk menyediakan ruang, lakukan OR pada bit itu, kemudian anjak n ke kanan.
Selepas 32 lelaran, integer output mengandungi semua 32 bit n dalam susunan terbalik. Ini ialah O(32) = O(1) bagi setiap panggilan, atau O(1) secara teramortisasi dengan penyimpanan sementara untuk panggilan berulang pada bahagian 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)) # 1Pembalikan Bit: Bahagi dan Takluk
Pendekatan O(log 32) = O(1) yang lebih pantas membalikkan bit menggunakan pertukaran bahagi dan takluk. Mula-mula tukar bit bersebelahan, kemudian kumpulan 2 bit bersebelahan, kemudian kumpulan 4 bit, dan seterusnya. Setiap peringkat pertukaran menggunakan topeng untuk mengasingkan kumpulan berselang-seli dan anjakan untuk menyelang-selikan kumpulan tersebut. Selepas 5 pertukaran, semua 32 bit diterbalikkan.
Pendekatan ini menggunakan operasi tetap O(1) tanpa mengira input dan digunakan dalam pelaksanaan perkakasan. Topeng itu ialah pemalar: 0x55555555 (corak 01 berselang-seli), 0x33333333 (0011 berselang-seli), 0x0f0f0f0f (00001111 berselang-seli) dan sebagainya.
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}')Bilangan Bit 1 (Berat Hamming)
Masalah Bilangan Bit 1 (LeetCode 191) meminta berat Hamming, iaitu bilangan bit 1, bagi integer tanpa tanda. Terdapat tiga pendekatan dengan pertukaran yang berbeza: gelung naif (O(32)), Brian Kernighan (O(k), dengan k = bit yang ditetapkan) dan n.bit_count() terbina dalam Python (3.10+).
Kaedah Brian Kernighan sering dipilih dalam temu duga kerana menunjukkan pemahaman tentang helah n & (n-1). Setiap lelaran membuang bit 1 terendah, jadi gelung berjalan tepat sebanyak bilangan bit 1 yang ada — jauh lebih pantas daripada imbasan penuh 32 bit untuk integer yang jarang.
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 Berturutan: Pendekatan Awalan
Kadang-kadang anda perlu mengira bit 1 dalam julat [l, r] dengan pantas. Bina jumlah awalan bit yang ditetapkan untuk 0..n: prefix[i] = prefix[i-1] + bin(i).count('1'). Kemudian kiraan bagi julat [l, r] ialah prefix[r] - prefix[l-1]. Ini membolehkan pertanyaan julat O(1) selepas prapemprosesan O(n).
Kaedah ini boleh digeneralisasikan kepada sebarang agregat berasaskan bit dalam sesuatu julat. Sebagai contoh, mengira nombor dalam [l, r] yang mempunyai bilangan bit yang ditetapkan genap menggunakan teknik awalan yang sama, tetapi dengan fungsi pengumpulan yang berbeza.
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)}')Pembalikan Bit untuk Nombor Negatif
Dalam Python, integer bertanda dan mempunyai lebar arbitrari. Apabila membalikkan bit untuk masalah LeetCode, kita mesti menganggap input sebagai integer tanpa tanda 32 bit. Topengkan input dengan & 0xFFFFFFFF sebelum memprosesnya untuk memastikan hanya 32 bit diambil kira. Output juga hendaklah berupa integer tanpa tanda 32 bit, iaitu bukan negatif.
Jika anda diberikan integer Python yang mungkin negatif, dalam pengertian pelengkap dua, gunakan & 0xFFFFFFFF terlebih dahulu untuk mendapatkan perwakilan tanpa tanda 32 bit, kemudian balikkan bitnya. Hasilnya sentiasa integer bukan negatif antara 0 hingga 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: Corak Pengiraan Bit
Masalah pengiraan bit mendedahkan corak umum bagi DP bit: jika anda mengetahui jawapan untuk versi i yang lebih kecil, anda boleh mengiranya untuk i menggunakan operasi bit yang mengambil masa malar. Corak ini boleh digeneralisasikan kepada masalah pengiraan bit lain, seperti mengira nombor yang mempunyai tepat k bit yang ditetapkan dalam [0, n] menggunakan penghitungan binari, atau kuasa dua tertinggi yang membahagi setiap nombor.
Satu lagi pemerhatian berguna: kiraan bit yang ditetapkan bagi i mengikuti corak berulang dalam setiap selang kuasa dua. Corak bagi [2^k, 2^(k+1) - 1] adalah sama seperti the [0, 2^k - 1] dengan setiap nilai ditambah 1, kerana bit k sentiasa ditetapkan dalam julat 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 Ketiga-tiganya: Latihan Bersepadu
Banyak masalah temu duga menggabungkan pengiraan bit, logik nombor hilang dan pembalikan bit dalam satu soalan. Sebagai contoh: diberikan tatasusunan yang elemennya ialah integer n-bit dan satu elemen hilang, cari nilai yang hilang. Atau: diberikan aliran kiraan bit, bina semula integer yang hilang. Masalah ini memerlukan anda mengenal pasti subteknik yang sesuai.
Berlatihlah membina peta mental: jika masalah menyebut pencarian elemen yang hilang, fikirkan XOR atau jumlah. Jika dikatakan 'kira bit 1 dengan cekap', fikirkan Kernighan atau DP. Jika dikatakan 'balikkan bit', fikirkan pendekatan lelaran atau bahagi dan takluk. Inilah tiga alat teras manipulasi bit dalam temu duga.
# 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}')Penyimpanan Sementara Bit untuk Pembalikan Bit
Untuk panggilan berulang bagi pembalikan bit, contohnya dalam simulasi perkakasan, simpan hasil untuk bahagian 8 bit dalam memori sementara. Oleh sebab setiap bait hanya boleh mempunyai 256 nilai, prakira hasil bait terbalik bagi setiap nilai 0-255. Untuk membalikkan integer 32 bit, pecahkannya kepada empat bahagian 8 bit, balikkan setiap bahagian dan cantumkan semula dalam susunan terbalik.
Ini mengurangkan setiap panggilan kepada empat carian jadual dan operasi bit — jauh lebih pantas daripada gelung 32 lelaran untuk pemprosesan pukal. Memori sementara itu dibina sekali dalam masa O(256 × 8) dan digunakan semula untuk semua panggilan seterusnya 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}')Semakan Pantas
Uji pemahaman anda tentang konsep Struktur Data & Algoritma — Persediaan Temu Duga Pengekodan daripada pelajaran ini.
Ringkasan Pelajaran
Dalam pelajaran ini anda telah mempelajari: pengiraan bit menggunakan DP dengan dp[i] = dp[i >> 1] + (i & 1) atau dp[i] = dp[i & (i-1)] + 1 untuk masa O(n), nombor hilang diselesaikan dalam O(n)/O(1) dengan melakukan XOR pada semua indeks bersama-sama semua nilai atau menggunakan formula jumlah aritmetik, dan pembalikan 32 bit dilakukan secara lelaran dalam O(32) atau dengan teknik topeng bahagi dan takluk. Seterusnya kita akan meneroka tindanan monotonik, bermula dengan invarian menaik berbanding menurun dan pertanyaan elemen lebih besar seterusnya.
Pelajari Persediaan Temu Duga Pengaturcaraan dengan tutor kecerdasan buatan — percuma
Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.
- Kursus
- 90
- Pelajaran
- 360
Soalan Lazim
Adakah pelajaran “Mengira Bit, Nombor Hilang dan Menterbalikkan Bit” percuma?
Ya — teks penuh “Mengira Bit, Nombor Hilang dan Menterbalikkan Bit” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus Persediaan Temu Duga Pengaturcaraan, tingkat taraf kepada CoddyKit PRO. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Apakah yang akan saya pelajari dalam “Mengira Bit, Nombor Hilang dan Menterbalikkan Bit”?
Kira bilangan bit bagi 0..n menggunakan DP dan helah bit-set terendah, cari nombor yang hilang melalui XOR, dan terbalikkan bit integer 32-bit. Anda berlatih Persediaan Temu Duga Pengaturcaraan menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.
Adakah saya memerlukan pengalaman untuk memulakan Persediaan Temu Duga Pengaturcaraan?
Tiada pengalaman terdahulu diperlukan. Pembelajaran Persediaan Temu Duga Pengaturcaraan di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 4 daripada 4.
Berapa lamakah pelajaran “Mengira Bit, Nombor Hilang dan Menterbalikkan Bit” diambil?
Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.
Bolehkah saya menulis dan menjalankan kod dalam pelajaran Persediaan Temu Duga Pengaturcaraan ini?
Ya. Setiap pelajaran Persediaan Temu Duga Pengaturcaraan menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.
Semua pelajaran dalam kursus ini
- Operator Bit: AND, OR, XOR, NOT, Anjakan
- Nombor Tunggal dan Sifat XOR
- Topeng Bit: Tetapkan, Kosongkan, Togol, Periksa
- Mengira Bit, Nombor Hilang dan Menterbalikkan Bit