Single Number e proprietà di XOR
Usi la proprietà di auto-inversione di XOR per trovare l'unico elemento che compare una volta in una lista in cui tutti gli altri compaiono due volte, quindi estenda il metodo a single-number-II e III.
Single Number e proprietà di XOR è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 2 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Il problema Single Number
Il problema Single Number (LeetCode 136) chiede di trovare, dato un array in cui ogni elemento compare esattamente due volte tranne uno, l'elemento che compare una sola volta. Il vincolo di tempo O(n) e spazio O(1) esclude le tabelle hash (spazio O(n)) e l'ordinamento (tempo O(n log n) o spazio O(n) per l'ordinamento).
La soluzione elegante usa XOR. Si applica XOR a tutti gli elementi. Poiché gli elementi identici si annullano (a ^ a = 0) e XOR è commutativo e associativo, tutte le coppie scompaiono e rimane solo l'elemento singolo. Questa è una delle soluzioni O(n)/O(1) più soddisfacenti di tutta la programmazione competitiva.
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])) # 1Perché XOR funziona: tre proprietà fondamentali
La potenza di XOR deriva dalla combinazione di tre proprietà algebriche:
- Inversa di sé stesso:
a ^ a = 0— i valori identici si annullano a vicenda - Elemento neutro:
a ^ 0 = a— applicare XOR a zero lascia invariati i valori - Commutatività e associatività: l'ordine non conta e nemmeno il raggruppamento
Insieme, queste tre proprietà fanno sì che lo XOR su un multinsieme riduca a 0 tutti gli elementi che compaiono un numero pari di volte, lasciando solo quelli che compaiono un numero dispari di volte. In Single Number I, esattamente un elemento compare una volta, cioè un numero dispari di volte, quindi è il risultato dello 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 resultAnalisi passo passo di Single Number
Analizziamo [4, 1, 2, 1, 2] passo dopo passo per vedere l'annullamento in azione. Applichiamo XOR a tutti gli elementi: 4 ^ 1 ^ 2 ^ 1 ^ 2. Poiché XOR è commutativo, possiamo riordinarli come (1 ^ 1) ^ (2 ^ 2) ^ 4 = 0 ^ 0 ^ 4 = 4. Le coppie si annullano e rimane soltanto 4.
Nell'algoritmo vero e proprio non riordiniamo gli elementi: applichiamo XOR da sinistra a destra. Il risultato finale è però lo stesso, perché commutatività e associatività garantiscono che l'ordine non influisca sull'esito. Può raggruppare mentalmente le coppie in qualsiasi posizione: si annulleranno tutte.
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')Single Number II: ogni elemento compare tre volte
Single Number II (LeetCode 137): ogni elemento compare tre volte, tranne uno che compare una sola volta. XOR da solo non funziona, perché le coppie non si annullano più quando gli elementi compaiono tre volte. Occorre invece contare quante volte compare ciascun bit considerando tutti i numeri. Se un bit compare nell'elemento cercato, contribuisce per 1; negli elementi ripetuti tre volte, contribuisce per 3. Si calcola count mod 3 per ogni bit, così da isolare i bit dell'elemento cercato.
Possiamo simulare questo comportamento con due variabili intere ones e twos, che fungono da contatore a livello di bit modulo 3. Si tratta di un approccio basato sulla logica digitale: ones contiene i bit osservati un numero dispari di volte modulo 2, mentre twos contiene i bit osservati due volte 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])) # 3Single Number III: due elementi compaiono una volta
Single Number III (LeetCode 260): due elementi compaiono una volta ciascuno, mentre tutti gli altri compaiono due volte. Applichiamo XOR a tutti gli elementi per ottenere a ^ b, cioè lo XOR dei due elementi unici. Poiché a ≠ b, almeno un bit di a ^ b è 1: troviamo il bit impostato meno significativo di a ^ b usando diff = xor_all & (-xor_all).
Questo bit vale 1 esattamente in uno tra a e b. Dividiamo tutti i numeri in due gruppi in base al fatto che quel bit sia impostato o meno. Applichiamo XOR separatamente a ciascun gruppo: gli elementi appaiati si annullano, lasciando a in un gruppo e b nell'altro.
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]Trovare il numero mancante con XOR
Il problema Missing Number (LeetCode 268) chiede di trovare, dato un array di n numeri distinti compresi tra 0 e n, quello mancante. Applichiamo XOR a tutti i numeri dell'array e a tutti i numeri da 0 a n. Le coppie si annullano, lasciando il numero mancante. Si ottengono così tempo O(n) e spazio O(1).
In alternativa, si può usare la formula della somma aritmetica: expected = n*(n+1)//2, quindi sottrarre la somma effettiva. Entrambi gli approcci hanno complessità O(n)/O(1). XOR è più robusto perché evita il possibile overflow degli interi nei linguaggi che usano interi di larghezza fissa.
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}')Scambiare valori con XOR senza variabile temporanea
XOR consente di scambiare due variabili senza usare una variabile temporanea. Il principio è che a ^ b ^ a = b e a ^ b ^ b = a. Si eseguono in sequenza tre assegnazioni XOR: a ^= b, poi b ^= a, infine a ^= b. Dopo tutte e tre, a contiene il valore originale di b e b contiene il valore originale di a.
È importante notare che questo trucco non funziona se a e b fanno riferimento alla stessa posizione di memoria, cioè se sono la stessa variabile. In tal caso, a ^= a imposta a su 0 e il valore viene perso. In Python, l'assegnazione tramite tupla (a, b = b, a) è più sicura e più chiara. Lo scambio con XOR è principalmente utile nei contesti C/embedded in cui non è disponibile memoria aggiuntiva.
# 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 nell'hashing e nei checksum
XOR è un componente fondamentale comune nei checksum e nei controlli di parità. Applicare XOR a tutti i byte di un blocco di dati produce un checksum di un byte. Se durante la trasmissione cambia un singolo bit, cambia anche il checksum, rilevando l'errore. È più semplice di CRC, ma rileva tutti gli errori di un singolo bit.
XOR viene usato anche nella parità RAID-5: per tre unità, si memorizza sulla terza lo XOR dei dati delle altre due. Se un'unità si guasta, si applica XOR alle due rimanenti per ricostruire i dati persi. È esattamente la logica di Single Number al contrario: l'unità di parità è l'«elemento unico» che codifica ciò che si annulla quando si applica XOR a tutte e tre le unità.
# 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 e problemi sui sottoinsiemi
XOR compare nei problemi sui sottoinsiemi quando è necessario calcolare lo XOR di tutti i sottoinsiemi. Un'osservazione fondamentale è che, per n elementi, ciascun elemento compare esattamente in 2^(n-1) sottoinsiemi. Se n > 1, ogni elemento compare un numero pari di volte, quindi il suo contributo XOR si annulla. Lo XOR di tutti gli XOR dei sottoinsiemi è 0 per n > 1.
Per n == 1, l'unico sottoinsieme non vuoto è l'elemento stesso, quindi lo XOR di tutti i sottoinsiemi è quell'elemento. Questo tipo di ragionamento, basato sulle proprietà di XOR e sul conteggio delle occorrenze, viene verificato nei problemi avanzati di manipolazione dei bit.
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}')Schema da colloquio: XOR per l'unicità
Riconosca lo schema XOR-per-l'unicità quando un problema afferma: «ogni elemento compare k volte tranne uno che compare m volte, dove m mod k != 0». Per k=2, m=1 (Single Number I), si applica XOR a tutti gli elementi. Per k=3, m=1 (Single Number II), si contano i bit modulo 3. Per k=2, m=1 con due elementi unici (Single Number III), si applica XOR e poi si dividono gli elementi in base al bit differente meno significativo.
L'approccio generale per un k arbitrario consiste nel contare il numero totale di occorrenze di ciascun bit e calcolarlo modulo k. Se il conteggio è diverso da zero, quel bit appartiene all'elemento unico. Si ottiene così un algoritmo O(32n) = O(n) con spazio O(1) per qualsiasi 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)) # 7Problemi comuni da colloquio su XOR
Oltre alla famiglia dei problemi sui numeri singoli, XOR compare spesso nei seguenti problemi:
- Find the Difference (LC 389): si applica XOR a tutti i caratteri di entrambe le stringhe; rimane il carattere aggiuntivo
- Hamming Distance (LC 461): si applica XOR a due numeri e si contano i bit 1 nel risultato
- Total Hamming Distance (LC 477): si contano gli 0 e gli 1 in ogni posizione di bit considerando tutte le coppie
- XOR Queries of a Subarray (LC 1310): si usa un array di XOR dei prefissi per le query sugli intervalli
In ciascun caso, la proprietà di annullamento di XOR elimina la ridondanza e riduce una soluzione brute force O(n²) a 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]]))Verifica rapida
Verifichi la sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep trattati in questa lezione.
Riepilogo della lezione
In questa lezione ha imparato che: la proprietà di inversa di sé stesso di XOR (a ^ a = 0) fa sì che gli elementi appaiati si annullino, lasciando solo l'elemento unico quando si applica XOR a tutti i numeri, che Single Number II usa il conteggio dei bit modulo 3, mentre Single Number III divide gli elementi in base al bit differente meno significativo e che XOR risolve anche i problemi del numero mancante, della ricerca della differenza, della distanza di Hamming e delle query XOR sugli intervalli. Ora esamineremo le maschere di bit per impostare, cancellare, invertire e verificare singoli bit.
Domande Frequenti
La lezione «Single Number e proprietà di XOR» è gratuita?
Sì — il testo completo di «Single Number e proprietà di XOR» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Single Number e proprietà di XOR»?
Usi la proprietà di auto-inversione di XOR per trovare l'unico elemento che compare una volta in una lista in cui tutti gli altri compaiono due volte, quindi estenda il metodo a single-number-II e II… Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 2 di 4.
Quanto tempo richiede la lezione «Single Number e proprietà di XOR»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Operatori bitwise: AND, OR, XOR, NOT e shift
- Single Number e proprietà di XOR
- Maschere di bit: impostare, azzerare, invertire e verificare
- Conteggio dei bit, numero mancante e inversione dei bit