Nombor Tunggal dan Sifat XOR
Gunakan sifat songsang kendiri XOR untuk mencari satu unsur yang muncul sekali dalam senarai apabila semua unsur lain muncul dua kali, kemudian kembangkan kepada single-number-II dan III.
Nombor Tunggal dan Sifat XOR ialah pelajaran DSA Interview Prep percuma di CoddyKit. Ini ialah pelajaran 2 daripada 4. Sebanyak 3 pelajaran dalam laluan pembelajaran ini boleh dibaca sepenuhnya secara percuma — selepas itu, CoddyKit PRO membuka akses kepada semua pelajaran, serta latihan praktikal dengan penyunting kod terbina dalam dan tutor kecerdasan buatan yang tersedia 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran DSA Interview Prep, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus DSA Interview Prep merangkumi sejumlah 4 pelajaran.
Masalah Nombor Tunggal
Masalah Nombor Tunggal (LeetCode 136) bertanya: diberikan satu tatasusunan yang setiap elemennya muncul tepat dua kali kecuali satu, cari elemen yang muncul sekali sahaja. Kekangan masa O(n) dan ruang O(1) menolak penggunaan peta cincang (ruang O(n)) serta pengisihan (masa O(n log n) atau ruang O(n) untuk pengisihan).
Penyelesaian yang elegan menggunakan XOR. Lakukan XOR pada semua elemen. Oleh sebab elemen yang sama saling membatalkan (a ^ a = 0) dan XOR bersifat komutatif serta asosiatif, semua elemen berpasangan hilang, lalu hanya elemen tunggal yang tinggal. Ini merupakan salah satu penyelesaian O(n)/O(1) yang paling memuaskan dalam seluruh pengaturcaraan kompetitif.
def single_number(nums):
result = 0
for n in nums:
result ^= n
return result
# All pairs cancel, leaving the lone element
print(single_number([2, 2, 1])) # 1
print(single_number([4, 1, 2, 1, 2])) # 4
print(single_number([1])) # 1
print(single_number([7, 3, 5, 3, 7])) # 5
# Even more concise with functools.reduce
from functools import reduce
from operator import xor
print(reduce(xor, [2, 2, 1])) # 1Mengapa XOR Berfungsi: Tiga Sifat Utama
Kuasa XOR berpunca daripada tiga sifat algebra yang saling melengkapi:
- Songsang diri:
a ^ a = 0— nilai yang sama saling membatalkan - Identiti:
a ^ 0 = a— XOR dengan sifar tidak mengubah nilai - Komutatif dan asosiatif: susunan tidak penting dan pengelompokan juga tidak penting
Ketiga-tiga sifat ini bersama-sama bermakna XOR pada koleksi yang boleh mengandungi ulangan akan mereduksi semua elemen yang muncul bilangan genap kali kepada 0, lalu hanya meninggalkan elemen yang muncul bilangan ganjil kali. Bagi Nombor Tunggal I, tepat satu elemen muncul sekali (bilangan ganjil), maka elemen itu ialah hasil XOR.
# Demonstrating the three XOR properties
print('Self-inverse: a ^ a = 0')
for a in [5, 13, 255, 0]:
print(f' {a} ^ {a} = {a ^ a}')
print('Identity: a ^ 0 = a')
for a in [5, 13, 0, 1024]:
print(f' {a} ^ 0 = {a ^ 0}')
print('Commutativity and Associativity:')
a, b, c = 3, 5, 7
print(f' a^b^c = {a^b^c}')
print(f' c^a^b = {c^a^b}') # same result
print(f' (a^b)^c = {(a^b)^c}')
print(f' a^(b^c) = {a^(b^c)}') # same resultMenelusuri Nombor Tunggal
Mari kita telusuri [4, 1, 2, 1, 2] langkah demi langkah untuk melihat pembatalan berlaku. Kita melakukan XOR pada semua elemen: 4 ^ 1 ^ 2 ^ 1 ^ 2. Oleh sebab XOR bersifat komutatif, susun semula sebagai (1 ^ 1) ^ (2 ^ 2) ^ 4 = 0 ^ 0 ^ 4 = 4. Pasangan-pasangan tersebut saling membatalkan dan hanya 4 yang tinggal.
Dalam algoritma sebenar, kita tidak menyusun semula elemen — kita melakukan XOR dari kiri ke kanan. Namun, hasil akhirnya tetap sama kerana sifat komutatif dan asosiatif menjamin bahawa susunan tidak mempengaruhi hasil. Anda boleh membayangkan pasangan-pasangan itu dikelompokkan di mana-mana sahaja dan semuanya akan saling membatalkan.
nums = [4, 1, 2, 1, 2]
result = 0
print(f'Start: result = {result} ({bin(result)})')
for n in nums:
prev = result
result ^= n
print(f'XOR {n:2d}: {bin(prev):8s} ^ {bin(n):6s} = {bin(result):8s} = {result}')
print(f'Final: {result}') # 4
# Alternative: show pair cancellation
print('\nMath view:')
print('4 ^ 1 ^ 2 ^ 1 ^ 2')
print('= 4 ^ (1^1) ^ (2^2)')
print('= 4 ^ 0 ^ 0')
print('= 4')Nombor Tunggal II: Setiap Elemen Muncul Tiga Kali
Nombor Tunggal II (LeetCode 137): setiap elemen muncul tiga kali kecuali satu elemen yang muncul sekali. XOR sahaja tidak berfungsi — pasangan tidak lagi saling membatalkan dalam kumpulan tiga. Sebaliknya, kita mengira berapa kali setiap bit muncul merentas semua nombor. Jika sesuatu bit muncul dalam elemen sasaran, sumbangannya ialah 1; dalam elemen yang muncul tiga kali, sumbangannya ialah 3. Ambil kiraan modulo 3 bagi setiap bit untuk mengasingkan bit-bit elemen sasaran.
Kita boleh mensimulasikannya menggunakan dua pemboleh ubah integer ones dan twos yang bertindak sebagai pembilang pada aras bit modulo 3. Ini ialah pendekatan logik digital: ones menyimpan bit yang dilihat bilangan ganjil kali modulo 2, manakala twos menyimpan bit yang dilihat dua kali modulo 3.
def single_number_II(nums):
ones, twos = 0, 0
for n in nums:
ones = (ones ^ n) & ~twos # bits seen 1 mod 3 times
twos = (twos ^ n) & ~ones # bits seen 2 mod 3 times
return ones # bits seen exactly once
print(single_number_II([2, 2, 3, 2])) # 3
print(single_number_II([0, 1, 0, 1, 0, 1, 99])) # 99
# Simpler but O(32) bit-by-bit approach
def single_number_II_simple(nums):
result = 0
for bit in range(32):
total = sum((n >> bit) & 1 for n in nums)
if total % 3 == 1:
result |= (1 << bit)
return result
print(single_number_II_simple([2, 2, 3, 2])) # 3Nombor Tunggal III: Dua Elemen Muncul Sekali
Nombor Tunggal III (LeetCode 260): dua elemen masing-masing muncul sekali, manakala semua elemen lain muncul dua kali. Lakukan XOR pada semua elemen untuk mendapatkan a ^ b (XOR bagi dua elemen unik tersebut). Oleh sebab a ≠ b, sekurang-kurangnya satu bit dalam a ^ b ialah 1 — cari bit 1 paling rendah bagi a ^ b menggunakan diff = xor_all & (-xor_all).
Bit ini ialah 1 dalam tepat satu daripada a atau b. Bahagikan semua nombor kepada dua kumpulan berdasarkan sama ada bit tersebut ditetapkan. Lakukan XOR pada setiap kumpulan secara berasingan — elemen berpasangan saling membatalkan, lalu a tinggal dalam satu kumpulan dan b dalam kumpulan yang lain.
def single_number_III(nums):
xor_all = 0
for n in nums:
xor_all ^= n # xor_all = a ^ b
diff = xor_all & (-xor_all) # isolate lowest differing bit
a = 0
for n in nums:
if n & diff: # group 1: has the diff bit set
a ^= n
b = xor_all ^ a # a ^ b ^ a = b
return [a, b]
print(sorted(single_number_III([1, 2, 1, 3, 2, 5]))) # [3, 5]
print(sorted(single_number_III([-1, 0]))) # [-1, 0]
print(sorted(single_number_III([0, 1]))) # [0, 1]Mencari Nombor yang Hilang dengan XOR
Masalah Nombor Hilang (LeetCode 268): diberikan satu tatasusunan yang mengandungi n nombor berbeza daripada 0 hingga n, cari nombor yang hilang. Lakukan XOR pada semua nombor dalam tatasusunan bersama-sama semua nombor dari 0 hingga n. Pasangan-pasangan saling membatalkan, lalu nombor yang hilang tinggal. Ini memberikan masa O(n) dan ruang O(1).
Sebagai alternatif, gunakan formula jumlah aritmetik: expected = n*(n+1)//2, kemudian tolak jumlah sebenar. Kedua-dua pendekatan mempunyai masa O(n) dan ruang O(1). XOR lebih teguh kerana mengelakkan kemungkinan limpahan integer dalam bahasa yang menggunakan integer dengan lebar tetap.
def missing_number_xor(nums):
n = len(nums)
result = n # start with n (the last expected value)
for i, num in enumerate(nums):
result ^= i ^ num # XOR with both index and value
return result
def missing_number_sum(nums):
n = len(nums)
expected = n * (n + 1) // 2
return expected - sum(nums)
for nums, expected in [([3,0,1], 2), ([0,1], 2), ([9,6,4,2,3,5,7,0,1], 8)]:
xor_ans = missing_number_xor(nums)
sum_ans = missing_number_sum(nums)
print(f'nums={nums}: XOR={xor_ans}, Sum={sum_ans}, expected={expected}')Menukar Nilai dengan XOR Tanpa Pemboleh Ubah Sementara
XOR membolehkan anda menukar dua pemboleh ubah tanpa pemboleh ubah sementara. Caranya ialah a ^ b ^ a = b dan a ^ b ^ b = a. Gunakan tiga penetapan XOR mengikut urutan: a ^= b, kemudian b ^= a, dan akhirnya a ^= b. Selepas ketiga-tiganya, a menyimpan nilai asal b dan b menyimpan nilai asal a.
Perhatian penting: kaedah ini gagal jika a dan b merujuk lokasi memori yang sama (iaitu, jika kedua-duanya ialah pemboleh ubah yang sama). Dalam keadaan itu, a ^= a menetapkan a kepada 0 dan nilainya hilang. Dalam Python, pembongkaran tuple (a, b = b, a) lebih selamat dan jelas. Penukaran dengan XOR paling berguna dalam konteks C atau sistem terbenam yang tidak mempunyai memori tambahan.
# XOR swap
a, b = 17, 42
print(f'Before: a={a}, b={b}')
a ^= b # a = 17 ^ 42
b ^= a # b = 42 ^ (17 ^ 42) = 17
a ^= b # a = (17 ^ 42) ^ 17 = 42
print(f'After: a={a}, b={b}') # a=42, b=17
# The caveat: same variable/reference => broken
c = 99
# If a and b pointed to same value:
c ^= c # c = 0 (destroyed!)
print(f'Same-variable XOR swap: c={c}') # 0, not 99
# Pythonic swap: always prefer this
a, b = 17, 42
a, b = b, a # safe, clear, handles aliases
print(f'Pythonic: a={a}, b={b}')XOR dalam Pencincangan dan Jumlah Semak
XOR ialah komponen asas yang biasa digunakan dalam jumlah semak dan semakan pariti. Melakukan XOR pada semua bait dalam satu blok data menghasilkan jumlah semak satu bait. Jika satu bit berubah semasa penghantaran, jumlah semak turut berubah lalu mengesan ralat tersebut. Kaedah ini lebih mudah daripada CRC tetapi dapat mengesan semua ralat satu bit.
XOR juga digunakan dalam pariti RAID-5: bagi tiga pemacu, simpan XOR data daripada dua pemacu pada pemacu ketiga. Jika satu pemacu gagal, lakukan XOR pada dua pemacu yang tinggal untuk membina semula data yang hilang. Ini tepat seperti logik Nombor Tunggal secara songsang — pemacu pariti ialah 'elemen unik' yang mengekod perkara yang terbatal apabila ketiga-tiganya dikenakan XOR.
# Simple XOR checksum
def xor_checksum(data):
result = 0
for byte in data:
result ^= byte
return result
data = [0x48, 0x65, 0x6C, 0x6C, 0x6F] # 'Hello' in ASCII
checksum = xor_checksum(data)
print(f'Checksum: {hex(checksum)}')
# Detect corruption
corrupted = data[:]
corrupted[2] ^= 0xFF # flip all bits of 3rd byte
new_checksum = xor_checksum(corrupted)
print(f'Original checksum: {hex(checksum)}')
print(f'Corrupted checksum: {hex(new_checksum)}')
print(f'Error detected: {checksum != new_checksum}')
# RAID-5 parity recovery
d1 = [1, 0, 1, 1]
d2 = [0, 1, 1, 0]
parity = [d1[i] ^ d2[i] for i in range(4)]
recovered = [parity[i] ^ d2[i] for i in range(4)] # recover d1
print(f'd1={d1}, parity={parity}, recovered={recovered}')XOR dan Masalah Subhimpunan
XOR muncul dalam masalah subhimpunan apabila anda perlu mengira XOR semua subhimpunan. Satu pemerhatian penting: bagi n elemen, setiap elemen muncul tepat 2^(n-1) kali dalam subhimpunan. Jika n > 1, setiap elemen muncul dalam bilangan subhimpunan yang genap, maka sumbangan XOR-nya saling membatalkan. XOR semua hasil XOR subhimpunan ialah 0 bagi n > 1.
Bagi n == 1, satu-satunya subhimpunan bukan kosong ialah elemen itu sendiri, maka XOR semua subhimpunan ialah elemen tersebut. Penaakulan seperti ini — menggunakan sifat XOR dan pengiraan — diuji dalam masalah manipulasi bit peringkat lanjutan.
from itertools import combinations
from functools import reduce
from operator import xor
def xor_of_all_subsets(arr):
n = len(arr)
total_xor = 0
for r in range(1, n + 1):
for subset in combinations(arr, r):
subset_xor = reduce(xor, subset)
total_xor ^= subset_xor
return total_xor
# For n > 1, each element appears 2^(n-1) times (even) => cancels
# Result is always 0 for n > 1
for arr in [[1,2,3], [5,7], [1], [1,2,3,4]]:
result = xor_of_all_subsets(arr)
predicted = arr[0] if len(arr) == 1 else 0
print(f'arr={arr}: XOR of all subsets = {result}, predicted = {predicted}')Corak Temu Duga: XOR untuk Keunikan
Kenal pasti corak XOR untuk keunikan apabila masalah menyatakan: 'setiap elemen muncul k kali kecuali satu yang muncul m kali, dengan m mod k != 0'. Bagi k=2, m=1 (Nombor Tunggal I): lakukan XOR pada semua elemen. Bagi k=3, m=1 (Nombor Tunggal II): kira bit modulo 3. Bagi k=2, m=1 dengan dua elemen unik (Nombor Tunggal III): lakukan XOR, kemudian bahagikan berdasarkan bit terendah yang berbeza.
Pendekatan umum bagi sebarang k ialah mengira jumlah kemunculan setiap bit dan mengambil modulo k. Jika kiraannya bukan sifar, bit tersebut ialah milik elemen unik. Ini memberikan algoritma O(32n) = O(n) dengan ruang O(1) untuk sebarang k.
def single_number_k_times(nums, k):
'''Find the element that appears m times when all others appear k times.'''
# Count each bit's occurrence and take mod k
result = 0
for bit in range(32):
total = sum((n >> bit) & 1 for n in nums)
if total % k != 0:
result |= (1 << bit)
# Handle negative 32-bit numbers
if result >= (1 << 31):
result -= (1 << 32)
return result
# k=2, element appears once
print(single_number_k_times([2,2,1], 2)) # 1
# k=3, element appears once
print(single_number_k_times([2,2,3,2], 3)) # 3
# k=4, element appears once
print(single_number_k_times([1,1,1,1,7,2,2,2,2], 4)) # 7Masalah Temu Duga XOR yang Lazim
Selain keluarga masalah nombor tunggal, XOR muncul dalam masalah yang kerap ditanya berikut:
- Cari Perbezaan (LC 389): lakukan XOR pada semua aksara bagi kedua-dua rentetan; aksara tambahan akan kekal
- Jarak Hamming (LC 461): lakukan XOR pada dua nombor, kemudian kira bit 1 dalam hasilnya
- Jumlah Jarak Hamming (LC 477): kira 0 dan 1 pada setiap kedudukan bit merentas semua pasangan
- Pertanyaan XOR pada Subtatasusunan (LC 1310): gunakan tatasusunan XOR awalan untuk pertanyaan julat
Dalam setiap kes, sifat pembatalan XOR menghapuskan lebihan dan mengurangkan kaedah cuba semua kemungkinan O(n²) kepada O(n).
# Find the difference between two strings
def find_the_difference(s, t):
result = 0
for c in s + t:
result ^= ord(c)
return chr(result)
print(find_the_difference('abcd', 'abcde')) # 'e'
# Hamming distance: count differing bits
def hamming_distance(x, y):
diff = x ^ y
count = 0
while diff:
count += diff & 1
diff >>= 1
return count
# or: bin(x ^ y).count('1')
print(hamming_distance(1, 4)) # 2: 001 vs 100 differ in bits 0 and 2
print(hamming_distance(3, 1)) # 1: 011 vs 001 differ in bit 1
# Prefix XOR for range queries
def xor_queries(arr, queries):
prefix = [0] * (len(arr) + 1)
for i, v in enumerate(arr):
prefix[i+1] = prefix[i] ^ v
return [prefix[r+1] ^ prefix[l] for l, r in queries]
print(xor_queries([1,3,4,8], [[0,1],[1,2],[0,3],[3,3]]))Semakan Pantas
Uji pemahaman anda tentang konsep Struktur Data & Algoritma — Persediaan Temu Duga Pengekodan daripada pelajaran ini.
Ulang Kaji Pelajaran
Dalam pelajaran ini anda telah belajar: sifat songsang diri XOR (a ^ a = 0) menyebabkan elemen berpasangan saling membatalkan, lalu hanya elemen unik yang tinggal apabila semua nombor dikenakan XOR, Nombor Tunggal II menggunakan pengiraan bit modulo 3, manakala Nombor Tunggal III membahagikan elemen berdasarkan bit terendah yang berbeza, dan XOR juga menyelesaikan masalah nombor hilang, mencari perbezaan, jarak Hamming dan pertanyaan XOR julat. Seterusnya, kita akan meneroka topeng bit untuk menetapkan, mengosongkan, menogol dan menyemak bit individu.
Pelajari Python 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
- 30
- Pelajaran
- 120
Soalan Lazim
Adakah pelajaran “Nombor Tunggal dan Sifat XOR” percuma?
Ya — sebanyak 3 pelajaran dalam laluan pembelajaran DSA Interview Prep, termasuk “Nombor Tunggal dan Sifat XOR”, boleh dibaca sepenuhnya secara percuma di web ini. Selepas itu, CoddyKit PRO membuka akses kepada semua pelajaran, serta latihan interaktif dengan penyunting kod terbina dalam dan tutor kecerdasan buatan yang tersedia 24/7. Kursus DSA Interview Prep merangkumi sejumlah 4 pelajaran.
Apakah yang akan saya pelajari dalam “Nombor Tunggal dan Sifat XOR”?
Gunakan sifat songsang kendiri XOR untuk mencari satu unsur yang muncul sekali dalam senarai apabila semua unsur lain muncul dua kali, kemudian kembangkan kepada single-number-II dan III. Anda berlatih DSA Interview Prep 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 DSA Interview Prep?
Tiada pengalaman terdahulu diperlukan. Pembelajaran DSA Interview Prep 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 2 daripada 4.
Berapa lamakah pelajaran “Nombor Tunggal dan Sifat XOR” 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 DSA Interview Prep ini?
Ya. Setiap pelajaran DSA Interview Prep 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