PricingLoginStart free
DSA Interview Prep · Lektion

Single Number og XOR-egenskaber

Brug XOR's selvinverse egenskab til at finde det ene element, der forekommer én gang i en liste, hvor alle andre forekommer to gange, og udvid derefter til single-number-II og III.

Lektion 2 af 413 trin

Single Number og XOR-egenskaber er en gratis DSA Interview Prep-lektion på CoddyKit. Dette er lektion 2 af 4. Du kan læse alle 3 lektioner i dette læringsspor gratis i deres fulde længde — derefter låser CoddyKit PRO alle lektioner op samt praktiske øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. Den er en del af læringsforløbet i DSA Interview Prep, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. DSA Interview Prep-kurset indeholder 4 lektioner i alt.

Problemet Single Number

Problemet Single Number (LeetCode 136) spørger: Givet et array, hvor hvert element forekommer præcis to gange bortset fra ét, skal du finde det element, der kun forekommer én gang. Kravet om O(n)-tid og O(1)-plads udelukker hash-tabeller (O(n)-plads) og sortering (O(n log n)-tid eller O(n)-plads til sorteringen).

Den elegante løsning bruger XOR. Udfør XOR på alle elementer. Da identiske elementer udligner hinanden (a ^ a = 0), og XOR er kommutativ og associativ, forsvinder alle parrede elementer, så kun det enkelte element er tilbage. Dette er en af de mest tilfredsstillende O(n)/O(1)-løsninger inden for konkurrenceprogrammering.

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]))  # 1

Hvorfor XOR virker: Tre nøgleegenskaber

XOR-operatorens styrke kommer fra tre algebraiske egenskaber, der virker sammen:

  • Selvinvers: a ^ a = 0 — identiske værdier udligner hinanden
  • Identitet: a ^ 0 = a — XOR med nul ændrer ikke værdierne
  • Kommutativitet og associativitet: rækkefølgen er ligegyldig, og grupperingerne er ligegyldige

Tilsammen betyder disse tre egenskaber, at XOR på en multimængde omdanner alle elementer, der forekommer et lige antal gange, til 0, så kun elementer, der forekommer et ulige antal gange, er tilbage. I Single Number I forekommer præcis ét element én gang (ulige), så det er XOR-resultatet.

# 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 result

Gennemgå Single Number

Lad os gennemgå [4, 1, 2, 1, 2] trin for trin for at se, hvordan udligningen fungerer. Vi udfører XOR på alle elementer: 4 ^ 1 ^ 2 ^ 1 ^ 2. Fordi XOR er kommutativ, kan vi omgruppere til (1 ^ 1) ^ (2 ^ 2) ^ 4 = 0 ^ 0 ^ 4 = 4. Parrene udligner hinanden, så kun 4 er tilbage.

I den faktiske algoritme omarrangerer vi ikke elementerne – vi udfører XOR fra venstre mod højre. Men slutresultatet er det samme, fordi kommutativitet og associativitet garanterer, at rækkefølgen ikke påvirker resultatet. Du kan mentalt gruppere parrene hvor som helst, og de udligner alle hinanden.

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: Hvert element forekommer tre gange

Single Number II (LeetCode 137): hvert element forekommer tre gange bortset fra ét, der forekommer én gang. XOR alene virker ikke – parrene udligner ikke længere hinanden i grupper på tre. I stedet tæller vi, hvor mange gange hver bit forekommer på tværs af alle tal. Hvis en bit forekommer i det ønskede element, bidrager den med 1; i elementer, der forekommer tre gange, bidrager den med 3. Tag count mod 3 for hver bit for at isolere det ønskede elements bits.

Vi kan simulere dette med to heltalsvariabler ones og twos, der fungerer som en bit-tæller modulo 3. Dette er en tilgang fra digital logik: ones indeholder bits, der er set et ulige antal gange modulo 2, og twos indeholder bits, der er set to gange 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]))  # 3

Single Number III: To elementer forekommer én gang

Single Number III (LeetCode 260): to elementer forekommer hver én gang, og alle andre forekommer to gange. Udfør XOR på alle elementer for at få a ^ b (XOR af de to entydige elementer). Eftersom a ≠ b, er mindst én bit i a ^ b lig med 1 – find den laveste satte bit i a ^ b ved hjælp af diff = xor_all & (-xor_all).

Denne bit er 1 i præcis ét af a og b. Opdel alle tal i to grupper baseret på, om denne bit er sat. Udfør XOR på hver gruppe separat – parrede elementer udligner hinanden, så a er tilbage i den ene gruppe og b i den anden.

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]

Find det manglende tal med XOR

Problemet Missing Number (LeetCode 268): Givet et array med n forskellige tal fra 0 til n skal du finde det manglende tal. Udfør XOR på alle tal i arrayet sammen med alle tal fra 0 til n. Parrene udligner hinanden, så det manglende tal er tilbage. Det giver O(n)-tid og O(1)-plads.

Alternativt kan du bruge den aritmetiske sumformel: expected = n*(n+1)//2 og derefter trække den faktiske sum fra. Begge fremgangsmåder har O(n)-tid og O(1)-plads. XOR er mere robust, fordi det undgår potentielt heltalsoverløb i sprog med heltal med fast bredde.

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}')

Byt om med XOR uden en midlertidig variabel

XOR gør det muligt at bytte om på to variabler uden en midlertidig variabel. Tricket er, at a ^ b ^ a = b og a ^ b ^ b = a. Anvend tre XOR-tildelinger i rækkefølge: a ^= b, derefter b ^= a og til sidst a ^= b. Efter alle tre indeholder a den oprindelige værdi af b, og b indeholder den oprindelige værdi af a.

Vigtigt forbehold: Dette trick mislykkes, hvis a og b refererer til den samme hukommelsesplacering (det vil sige, hvis de er den samme variabel). I så fald sætter a ^= a a til 0, og værdien går tabt. I Python er tuple-udpakning (a, b = b, a) sikrere og tydeligere. XOR-ombytning er især nyttig i C- og indlejrede systemer uden ekstra hukommelse.

# 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 i hashberegning og kontrolsummer

XOR er en almindelig byggesten i kontrolsummer og paritetskontroller. Hvis du udfører XOR på alle bytes i en datablok, får du en kontrolsum på én byte. Hvis en enkelt bit skifter under overførsel, ændres kontrolsummen, så fejlen opdages. Dette er enklere end CRC, men registrerer alle enkeltbitfejl.

XOR bruges også i RAID-5-paritet: For tre drev lagres XOR af dataene fra to drev på det tredje. Hvis et drev svigter, udfører du XOR på de to resterende drev for at genskabe de mistede data. Dette er præcis Single Number-logikken bagfra – paritetsdrevet er det 'entydige element', der koder for det, som udlignes, når XOR udføres på alle tre.

# 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 og delmængdeproblemer

XOR forekommer i problemer med delmængder, når du skal beregne XOR for alle delmængder. En vigtig indsigt er, at hvert element for n elementer forekommer i præcis 2^(n-1) delmængder. Hvis n > 1, forekommer hvert element i et lige antal delmængder, så dets XOR-bidrag udlignes. XOR af alle delmængdernes XOR er 0 for n > 1.

For n == 1 er den eneste ikke-tomme delmængde selve elementet, så XOR af alle delmængder er dette element. Denne form for ræsonnement – at bruge XOR-egenskaber og optælling – afprøves i avancerede problemer med bitmanipulation.

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}')

Interviewmønster: XOR til at finde entydighed

Genkend mønsteret XOR til at finde entydighed, når et problem siger: 'hvert element forekommer k gange bortset fra ét, der forekommer m gange, hvor m mod k != 0'. For k=2, m=1 (Single Number I): udfør XOR på alle elementer. For k=3, m=1 (Single Number II): tæl bits modulo 3. For k=2, m=1 med to entydige elementer (Single Number III): udfør XOR, og opdel derefter efter den laveste bit, der er forskellig.

Den generelle fremgangsmåde for vilkårlig k er at tælle det samlede antal forekomster af hver bit og tage modulo k. Hvis optællingen ikke er nul, tilhører den bit det entydige element. Det giver en O(32n) = O(n)-algoritme med O(1)-plads for enhver 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))  # 7

Almindelige XOR-problemer til interviews

Ud over familien af Single Number-problemer optræder XOR i disse ofte stillede problemer:

  • Find the Difference (LC 389): udfør XOR på alle tegn i begge strenge; det ekstra tegn bliver tilbage
  • Hamming Distance (LC 461): udfør XOR på to tal, og tæl 1-bits i resultatet
  • Total Hamming Distance (LC 477): tæl 0'er og 1'er ved hver bitposition på tværs af alle par
  • XOR Queries of a Subarray (LC 1310): brug et præfiks-XOR-array til intervalforespørgsler

I hvert tilfælde eliminerer XOR-operatorens udligningsegenskab overflødighed og reducerer en O(n²)-brute force-løsning til 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]]))

Hurtig kontrol

Kontrollér din forståelse af begreberne fra Data Structures & Algorithms — Coding Interview Prep i denne lektion.

Besvar den i den interaktive lektion

Opsummering af lektionen

I denne lektion lærte du: XOR's selvinverse egenskab (a ^ a = 0) får parrede elementer til at udligne hinanden, så kun det entydige element er tilbage, når alle tal kombineres med XOR, Single Number II bruger bitoptælling modulo 3, mens Single Number III opdeler elementerne efter den laveste bit, der er forskellig, og XOR løser også problemerne med manglende tal, forskel, Hamming-afstand og XOR-forespørgsler på intervaller. Næste gang ser vi på bitmasker til at sætte, rydde, skifte og kontrollere enkelte bits.

Gratis at komme i gang

Lær Python med en AI-underviser — gratis

Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.

Kurser
30
Lektioner
120
Start gratisSe hele kurset

Ofte stillede spørgsmål

Er lektionen “Single Number og XOR-egenskaber” gratis?

Ja — alle 3 lektioner i læringssporet DSA Interview Prep, inklusive “Single Number og XOR-egenskaber”, kan læses gratis i deres fulde længde her på webstedet. Derefter låser CoddyKit PRO alle lektioner op samt interaktive øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. DSA Interview Prep-kurset indeholder 4 lektioner i alt.

Hvad lærer jeg i “Single Number og XOR-egenskaber”?

Brug XOR's selvinverse egenskab til at finde det ene element, der forekommer én gang i en liste, hvor alle andre forekommer to gange, og udvid derefter til single-number-II og III. Du øver dig i DSA Interview Prep med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.

Skal jeg have erfaring for at begynde på DSA Interview Prep?

Der kræves ingen tidligere erfaring. DSA Interview Prep på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 2 af 4.

Hvor lang tid tager lektionen “Single Number og XOR-egenskaber”?

De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.

Kan jeg skrive og køre kode i denne DSA Interview Prep-lektion?

Ja. Alle DSA Interview Prep-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.

Alle lektioner i dette kursus

  1. Bitvise operatorer: AND, OR, XOR, NOT og skift
  2. Single Number og XOR-egenskaber
  3. Bitmasker: Sæt, ryd, skift og kontrollér
  4. Optælling af bit, manglende tal og omvendte bit
← Tilbage til DSA Interview Prep