Single Number i właściwości XOR
Wykorzystywać właściwość samoodwrotności XOR do znalezienia jedynego elementu występującego raz na liście, na której wszystkie pozostałe elementy występują dwukrotnie, a następnie rozszerzyć rozwiązanie na single-number-II i III
Single Number i właściwości XOR to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 2 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 Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Problem pojedynczej liczby
Problem pojedynczej liczby (LeetCode 136) polega na tym, że dana jest tablica, w której każdy element występuje dokładnie dwa razy poza jednym. Należy znaleźć element występujący tylko raz. Ograniczenia czasu O(n) i pamięci O(1) wykluczają użycie tablic mieszających (pamięć O(n)) oraz sortowania (czas O(n log n) lub pamięć O(n) na potrzeby sortowania).
Eleganckie rozwiązanie wykorzystuje operację XOR. Wykonaj XOR na wszystkich elementach. Ponieważ identyczne elementy znoszą się wzajemnie (a ^ a = 0), a XOR jest przemienny i łączny, wszystkie pary znikają, pozostawiając tylko pojedynczy element. To jedno z najbardziej satysfakcjonujących rozwiązań o złożoności O(n)/O(1) w całym programowaniu konkursowym.
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])) # 1Dlaczego XOR działa: trzy kluczowe właściwości
Moc XOR wynika ze współdziałania trzech właściwości algebraicznych:
- Samoodwrotność:
a ^ a = 0— identyczne wartości znoszą się wzajemnie - Element neutralny:
a ^ 0 = a— wykonanie XOR z zerem nie zmienia wartości - Przemienność i łączność: kolejność nie ma znaczenia, podobnie jak sposób grupowania
Te trzy właściwości razem oznaczają, że wykonanie XOR na multizbiorze sprowadza wszystkie elementy występujące parzystą liczbę razy do 0, pozostawiając tylko elementy występujące nieparzystą liczbę razy. W przypadku problemu pojedynczej liczby I dokładnie jeden element występuje raz, czyli nieparzystą liczbę razy, dlatego jest wynikiem operacji 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 resultPrześledzenie problemu pojedynczej liczby
Prześledźmy krok po kroku przykład [4, 1, 2, 1, 2], aby zobaczyć znoszenie się elementów w działaniu. Wykonujemy XOR na wszystkich elementach: 4 ^ 1 ^ 2 ^ 1 ^ 2. Ponieważ XOR jest przemienny, możemy zmienić kolejność: (1 ^ 1) ^ (2 ^ 2) ^ 4 = 0 ^ 0 ^ 4 = 4. Pary znoszą się, pozostawiając tylko 4.
W rzeczywistym algorytmie nie zmieniamy kolejności — wykonujemy XOR od lewej do prawej. Wynik końcowy jest jednak taki sam, ponieważ przemienność i łączność gwarantują, że kolejność nie wpływa na rezultat. Można wyobrażeniowo grupować pary w dowolnych miejscach, a wszystkie się zniosą.
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')Problem pojedynczej liczby II: każdy element występuje trzy razy
Problem pojedynczej liczby II (LeetCode 137): każdy element występuje trzy razy poza jednym, który występuje raz. Sam XOR nie wystarcza — pary nie znoszą się już w grupach po trzy. Zamiast tego zliczamy, ile razy każdy bit występuje we wszystkich liczbach. Jeśli bit występuje w docelowym elemencie, wnosi 1; w elementach występujących trzykrotnie wnosi 3. Dla każdego bitu obliczamy count mod 3, aby wyodrębnić bity docelowego elementu.
Można zasymulować to za pomocą dwóch zmiennych całkowitych ones i twos, które działają jak licznik na poziomie bitów modulo 3. Jest to podejście oparte na logice cyfrowej: ones przechowuje bity napotkane nieparzystą liczbę razy modulo 2, a twos przechowuje bity napotkane dwukrotnie 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])) # 3Problem pojedynczej liczby III: dwa elementy występują raz
Problem pojedynczej liczby III (LeetCode 260): dwa elementy występują po jednym razie, a wszystkie pozostałe występują dwukrotnie. Wykonaj XOR na wszystkich elementach, aby otrzymać a ^ b (XOR dwóch unikatowych elementów). Ponieważ a ≠ b, co najmniej jeden bit w a ^ b ma wartość 1 — znajdź najniższy ustawiony bit wartości a ^ b za pomocą diff = xor_all & (-xor_all).
Ten bit ma wartość 1 dokładnie w jednym z elementów a i b. Podziel wszystkie liczby na dwie grupy w zależności od tego, czy ten bit jest ustawiony. Wykonaj XOR osobno dla każdej grupy — sparowane elementy się zniosą, pozostawiając a w jednej grupie i b w drugiej.
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]Znajdowanie brakującej liczby za pomocą XOR
Problem brakującej liczby (LeetCode 268): dana jest tablica n różnych liczb z zakresu od 0 do n. Należy znaleźć brakującą liczbę. Wykonaj XOR na wszystkich liczbach z tablicy oraz na wszystkich liczbach od 0 do n. Pary się zniosą, pozostawiając brakującą liczbę. Otrzymujemy czas O(n) i pamięć O(1).
Alternatywnie można użyć wzoru na sumę arytmetyczną: expected = n*(n+1)//2, a następnie odjąć rzeczywistą sumę. Oba podejścia mają złożoność O(n)/O(1). XOR jest bardziej niezawodny, ponieważ pozwala uniknąć potencjalnego przepełnienia liczby całkowitej w językach używających liczb całkowitych o stałej szerokości.
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}')Zamiana za pomocą XOR bez zmiennej tymczasowej
XOR umożliwia zamianę dwóch zmiennych bez użycia zmiennej tymczasowej. Sztuczka polega na tym, że a ^ b ^ a = b oraz a ^ b ^ b = a. Wykonaj kolejno trzy przypisania z XOR: a ^= b, następnie b ^= a, a na końcu a ^= b. Po wykonaniu wszystkich trzech operacji a przechowuje pierwotną wartość b, a b — pierwotną wartość a.
Ważne zastrzeżenie: ta sztuczka nie działa, jeśli a i b wskazują tę samą lokalizację pamięci, czyli są tą samą zmienną. W takim przypadku a ^= a ustawia a na 0 i wartość zostaje utracona. W Pythonie bezpieczniejsze i bardziej czytelne jest rozpakowywanie krotek (a, b = b, a). Zamiana za pomocą XOR jest przydatna głównie w kontekście C i systemów wbudowanych, gdzie nie można użyć dodatkowej pamięci.
# 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 w haszowaniu i sumach kontrolnych
XOR jest często używany jako element składowy sum kontrolnych i testów parzystości. Wykonanie XOR na wszystkich bajtach bloku danych tworzy jednobajtową sumę kontrolną. Jeśli podczas transmisji zmieni się pojedynczy bit, suma kontrolna również się zmieni, wykrywając błąd. Jest to prostsze rozwiązanie niż CRC, ale wykrywa wszystkie błędy pojedynczego bitu.
XOR jest również używany w mechanizmie parzystości RAID-5: dla trzech dysków na trzecim przechowuje się XOR danych z dwóch pozostałych dysków. Jeśli jeden dysk ulegnie awarii, wykonanie XOR na dwóch pozostałych pozwala odtworzyć utracone dane. To dokładnie logika problemu pojedynczej liczby zastosowana odwrotnie — dysk z parzystością jest „unikatowym elementem”, który koduje informacje o tym, co znosi się podczas wykonania XOR na wszystkich trzech elementach.
# 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 i problemy z podzbiorami
XOR pojawia się w problemach z podzbiorami, gdy trzeba obliczyć XOR wszystkich podzbiorów. Kluczowa obserwacja: dla n elementów każdy element występuje dokładnie w 2^(n-1) podzbiorach. Jeśli n > 1, każdy element występuje w parzystej liczbie podzbiorów, więc jego wkład w XOR się znosi. XOR wszystkich wartości XOR podzbiorów wynosi 0 dla n > 1.
Dla n == 1 jedynym niepustym podzbiorem jest sam element, więc XOR wszystkich podzbiorów jest równy temu elementowi. Tego rodzaju rozumowanie — wykorzystujące właściwości XOR i zliczanie — jest sprawdzane w zaawansowanych zadaniach z operacji bitowych.
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}')Wzorzec rekrutacyjny: XOR do znajdowania unikatowości
Rozpoznaj wzorzec XOR służący do znajdowania unikatowości, gdy treść zadania mówi: „każdy element występuje k razy poza jednym, który występuje m razy, gdzie m mod k != 0”. Dla k=2, m=1 (problem pojedynczej liczby I) wykonaj XOR na wszystkich elementach. Dla k=3, m=1 (problem pojedynczej liczby II) zliczaj bity modulo 3. Dla k=2, m=1 i dwóch unikatowych elementów (problem pojedynczej liczby III) wykonaj XOR, a następnie podziel elementy według najniższego różniącego bitu.
Ogólne podejście dla dowolnego k polega na zliczeniu łącznej liczby wystąpień każdego bitu i obliczeniu reszty modulo k. Jeśli licznik jest różny od zera, dany bit należy do unikatowego elementu. Otrzymujemy algorytm O(32n) = O(n) ze stałą pamięcią O(1) dla dowolnego 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)) # 7Typowe zadania rekrutacyjne z użyciem XOR
Poza rodziną problemów z pojedynczą liczbą XOR pojawia się w następujących często spotykanych zadaniach:
- Znajdowanie różnicy (LC 389): wykonaj XOR na wszystkich znakach obu napisów; dodatkowy znak pozostanie
- Odległość Hamminga (LC 461): wykonaj XOR na dwóch liczbach i policz bity o wartości 1 w wyniku
- Łączna odległość Hamminga (LC 477): zlicz zera i jedynki na każdej pozycji bitu we wszystkich parach
- Zapytania XOR dla podtablicy (LC 1310): użyj tablicy prefiksowych wartości XOR dla zapytań dotyczących przedziałów
W każdym przypadku właściwość znoszenia się elementów przez XOR eliminuje nadmiarowość i redukuje rozwiązanie siłowe O(n²) do 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]]))Szybkie sprawdzenie
Sprawdź swoją wiedzę na temat koncepcji z kursu Data Structures & Algorithms — Coding Interview Prep przedstawionych w tej lekcji.
Podsumowanie lekcji
W tej lekcji nauczyli się Państwo, że samoodwrotność XOR (a ^ a = 0) powoduje znoszenie się sparowanych elementów, pozostawiając tylko unikatowy element podczas wykonywania XOR na wszystkich liczbach, że w problemie pojedynczej liczby II używa się zliczania bitów modulo 3, a w problemie pojedynczej liczby III dzieli się elementy według najniższego różniącego bitu oraz że XOR rozwiązuje również problemy brakującej liczby, znajdowania różnicy, odległości Hamminga i zapytań XOR dla przedziałów. Następnie zajmiemy się maskami bitowymi służącymi do ustawiania, zerowania, przełączania i sprawdzania poszczególnych bitów.
Często zadawane pytania
Czy lekcja „Single Number i właściwości XOR” jest bezpłatna?
Tak — pełny tekst „Single Number i właściwości XOR” 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 Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Single Number i właściwości XOR”?
Wykorzystywać właściwość samoodwrotności XOR do znalezienia jedynego elementu występującego raz na liście, na której wszystkie pozostałe elementy występują dwukrotnie, a następnie rozszerzyć rozwiąza… Ćwiczysz Coding 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ąć Coding Interview Prep?
Nie wymagamy żadnego doświadczenia. Coding 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 2 z 4.
Ile czasu zajmuje lekcja „Single Number i właściwości XOR”?
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 Coding Interview Prep?
Tak. Każda lekcja Coding 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