Single Number und XOR-Eigenschaften
Nutzen Sie die Selbstinversen-Eigenschaft von XOR, um das einzige Element zu finden, das in einer Liste einmal vorkommt, während alle anderen zweimal vorkommen, und erweitern Sie dies auf single-number-II und III.
Single Number und XOR-Eigenschaften ist eine kostenlose DSA Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 2 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des DSA Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Das Problem „Single Number“
Beim Problem Single Number (LeetCode 136) ist ein Array gegeben, in dem jedes Element genau zweimal vorkommt – mit Ausnahme eines Elements. Finden Sie dieses Element, das nur einmal vorkommt. Die Vorgaben von O(n) Laufzeit und O(1) Speicherplatz schließen Hashmaps (O(n) Speicherplatz) und Sortieren aus (O(n log n) Laufzeit oder O(n) Speicherplatz für das Sortieren).
Die elegante Lösung verwendet XOR. Verknüpfen Sie alle Elemente per XOR miteinander. Da identische Elemente sich aufheben (a ^ a = 0) und XOR kommutativ sowie assoziativ ist, verschwinden alle Elementpaare, sodass nur das einzelne Element übrig bleibt. Dies ist eine der befriedigendsten O(n)/O(1)-Lösungen in der gesamten kompetitiven Programmierung.
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])) # 1Warum XOR funktioniert: Drei wichtige Eigenschaften
Die Stärke von XOR beruht auf drei algebraischen Eigenschaften, die zusammenwirken:
- Selbstinvers:
a ^ a = 0– identische Werte heben sich gegenseitig auf - Neutrales Element:
a ^ 0 = a– XOR mit null lässt Werte unverändert - Kommutativ und assoziativ: Die Reihenfolge und die Gruppierung spielen keine Rolle
Diese drei Eigenschaften bedeuten zusammen, dass XOR über eine Multimenge alle Elemente, die eine gerade Anzahl von Malen vorkommen, zu 0 reduziert. Übrig bleiben nur die Elemente, die eine ungerade Anzahl von Malen vorkommen. Bei Single Number I kommt genau ein Element einmal vor (ungerade oft), daher ist es das XOR-Ergebnis.
# 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 resultSingle Number Schritt für Schritt nachvollziehen
Betrachten wir [4, 1, 2, 1, 2] Schritt für Schritt, um die Aufhebung in Aktion zu sehen. Wir verknüpfen alle Elemente per XOR: 4 ^ 1 ^ 2 ^ 1 ^ 2. Da XOR kommutativ ist, können wir die Reihenfolge zu (1 ^ 1) ^ (2 ^ 2) ^ 4 = 0 ^ 0 ^ 4 = 4 ändern. Die Paare heben sich auf, und nur 4 bleibt übrig.
Im eigentlichen Algorithmus ändern wir die Reihenfolge nicht, sondern verknüpfen die Elemente von links nach rechts per XOR. Das Endergebnis ist jedoch dasselbe, weil Kommutativität und Assoziativität garantieren, dass die Reihenfolge das Ergebnis nicht beeinflusst. Sie können die Paare gedanklich beliebig gruppieren – sie heben sich immer auf.
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: Jedes Element kommt dreimal vor
Bei Single Number II (LeetCode 137) kommt jedes Element dreimal vor, mit Ausnahme eines Elements, das einmal vorkommt. XOR allein funktioniert nicht – bei Dreiergruppen heben sich die Elemente nicht mehr paarweise auf. Stattdessen zählen wir, wie oft jedes Bit in allen Zahlen vorkommt. Wenn ein Bit im Zielelement vorkommt, trägt es 1 bei; bei Elementen, die dreimal vorkommen, trägt es 3 bei. Wenden Sie für jedes Bit count mod 3 an, um die Bits des Zielelements zu isolieren.
Wir können dies mit zwei ganzzahligen Variablen ones und twos simulieren, die als Bitzähler modulo 3 dienen. Dieser Ansatz stammt aus der Digitallogik: ones enthält die Bits, die modulo 2 ungerade oft gesehen wurden, und twos enthält die Bits, die modulo 3 zweimal gesehen wurden.
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: Zwei Elemente kommen einmal vor
Bei Single Number III (LeetCode 260) kommt jedes von zwei Elementen genau einmal vor, alle anderen kommen zweimal vor. Verknüpfen Sie alle Elemente per XOR, um a ^ b zu erhalten (das XOR der beiden eindeutigen Elemente). Da a ≠ b gilt, ist mindestens ein Bit in a ^ b gleich 1. Finden Sie das niedrigstwertige gesetzte Bit von a ^ b mit diff = xor_all & (-xor_all).
Dieses Bit ist genau in einem der beiden Elemente a oder b gleich 1. Teilen Sie alle Zahlen anhand dessen, ob dieses Bit gesetzt ist, in zwei Gruppen auf. Verknüpfen Sie jede Gruppe separat per XOR – die Paare heben sich auf, sodass a in der einen und b in der anderen Gruppe übrig bleibt.
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]Die fehlende Zahl mit XOR finden
Beim Problem Missing Number (LeetCode 268) ist ein Array mit n verschiedenen Zahlen aus dem Bereich von 0 bis n gegeben. Finden Sie die fehlende Zahl. Verknüpfen Sie alle Zahlen im Array per XOR mit allen Zahlen von 0 bis n. Die Paare heben sich auf, sodass die fehlende Zahl übrig bleibt. Dies ergibt O(n) Laufzeit und O(1) Speicherplatz.
Alternativ können Sie die arithmetische Summenformel verwenden: expected = n*(n+1)//2, und anschließend die tatsächliche Summe abziehen. Beide Ansätze haben eine Laufzeit von O(n) und benötigen O(1) Speicherplatz. XOR ist robuster, weil dadurch ein möglicher Ganzzahlüberlauf in Sprachen mit Ganzzahlen fester Breite vermieden wird.
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}')XOR zum Vertauschen ohne temporäre Variable
XOR ermöglicht es, zwei Variablen ohne temporäre Variable zu vertauschen. Der entscheidende Zusammenhang ist a ^ b ^ a = b und a ^ b ^ b = a. Führen Sie drei XOR-Zuweisungen nacheinander aus: zuerst a ^= b, dann b ^= a und anschließend a ^= b. Danach enthält a den ursprünglichen Wert von b und b den ursprünglichen Wert von a.
Wichtiger Hinweis: Dieser Trick funktioniert nicht, wenn a und b auf dieselbe Speicherstelle verweisen, also dieselbe Variable sind. In diesem Fall setzt a ^= a a auf 0, und der Wert geht verloren. In Python ist die Tupelzuweisung (a, b = b, a) sicherer und verständlicher. Der XOR-Tausch ist vor allem in C- und Embedded-Kontexten ohne zusätzlichen Speicher nützlich.
# 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 bei Hashing und Prüfsummen
XOR ist ein häufig verwendeter Baustein bei Prüfsummen und Paritätsprüfungen. Wenn Sie alle Bytes eines Datenblocks per XOR verknüpfen, entsteht eine ein Byte große Prüfsumme. Wenn bei der Übertragung ein einzelnes Bit kippt, ändert sich die Prüfsumme, wodurch der Fehler erkannt wird. Das ist einfacher als CRC, erkennt aber alle Einzelbitfehler.
XOR wird auch bei der RAID-5-Parität verwendet: Bei drei Laufwerken speichern Sie das XOR der Daten zweier Laufwerke auf dem dritten. Wenn ein Laufwerk ausfällt, können Sie die verlorenen Daten durch XOR der beiden verbleibenden Laufwerke rekonstruieren. Das ist genau die Logik von Single Number in umgekehrter Richtung – das Paritätslaufwerk ist das „eindeutige Element“, das codiert, was sich beim XOR aller drei Werte aufhebt.
# 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 und Teilmengenprobleme
XOR kommt bei Teilmengenproblemen zum Einsatz, wenn Sie das XOR aller Teilmengen berechnen müssen. Eine wichtige Erkenntnis: Bei n Elementen kommt jedes Element in genau 2^(n-1) Teilmengen vor. Für n > 1 kommt daher jedes Element in einer geraden Anzahl von Teilmengen vor, sodass sein XOR-Beitrag sich aufhebt. Das XOR aller Teilmengen-XORs ist für n > 1 gleich 0.
Für n == 1 ist die einzige nichtleere Teilmenge das Element selbst, daher entspricht das XOR aller Teilmengen diesem Element. Eine solche Argumentation – die Eigenschaften von XOR mit Zählen zu verbinden – wird in anspruchsvollen Problemen zur Bitmanipulation geprüft.
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}')Interviewmuster: XOR für Eindeutigkeit
Erkennen Sie das Muster „XOR für Eindeutigkeit“, wenn ein Problem besagt: „Jedes Element kommt k-mal vor, mit Ausnahme eines Elements, das m-mal vorkommt, wobei m mod k != 0 gilt“. Für k=2 und m=1 (Single Number I): Verknüpfen Sie alle Elemente per XOR. Für k=3 und m=1 (Single Number II): Zählen Sie die Bits modulo 3. Für k=2 und m=1 mit zwei eindeutigen Elementen (Single Number III): Führen Sie zunächst XOR aus und teilen Sie dann anhand des niedrigstwertigen unterschiedlichen Bits auf.
Der allgemeine Ansatz für beliebige Werte von k besteht darin, die Gesamtanzahl jedes Bits zu zählen und modulo k zu nehmen. Wenn der Zähler ungleich null ist, gehört dieses Bit zum eindeutigen Element. So erhalten Sie für jedes k einen O(32n) = O(n)-Algorithmus mit O(1) Speicherplatz.
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)) # 7Häufige XOR-Interviewprobleme
Neben der Single-Number-Familie kommt XOR in den folgenden häufig gestellten Problemen zum Einsatz:
- Find the Difference (LC 389): Verknüpfen Sie alle Zeichen beider Zeichenketten per XOR; das zusätzliche Zeichen bleibt übrig
- Hamming Distance (LC 461): Verknüpfen Sie zwei Zahlen per XOR und zählen Sie die 1-Bits im Ergebnis
- Total Hamming Distance (LC 477): Zählen Sie an jeder Bitposition die Nullen und Einsen über alle Paare hinweg
- XOR Queries of a Subarray (LC 1310): Verwenden Sie für Bereichsabfragen ein Präfix-XOR-Array
In jedem Fall beseitigt die Aufhebungseigenschaft von XOR Redundanz und reduziert eine O(n²)-Brute-Force-Lösung auf 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]]))Schnelltest
Testen Sie Ihr Verständnis der Konzepte aus dieser Lektion zu Datenstrukturen und Algorithmen – Vorbereitung auf Coding-Interviews.
Lektionsrückblick
In dieser Lektion haben Sie gelernt: Die Selbstinvers-Eigenschaft von XOR (a ^ a = 0) bewirkt, dass sich gepaarte Elemente aufheben, sodass beim XOR aller Zahlen nur das eindeutige Element übrig bleibt, Single Number II verwendet Bitzählung modulo 3, während Single Number III die Elemente anhand des niedrigstwertigen unterschiedlichen Bits aufteilt, und XOR löst außerdem die Probleme Missing Number, Find the Difference, Hamming Distance und Bereichsabfragen mit XOR. Als Nächstes sehen wir uns Bitmasken zum Setzen, Löschen, Umschalten und Prüfen einzelner Bits an.
Häufig gestellte Fragen
Ist die Lektion „Single Number und XOR-Eigenschaften“ kostenlos?
Ja — der vollständige Text von „Single Number und XOR-Eigenschaften“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des DSA Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Single Number und XOR-Eigenschaften“?
Nutzen Sie die Selbstinversen-Eigenschaft von XOR, um das einzige Element zu finden, das in einer Liste einmal vorkommt, während alle anderen zweimal vorkommen, und erweitern Sie dies auf single-numb… Du übst DSA Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um DSA Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. DSA Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 2 von 4.
Wie lange dauert die Lektion „Single Number und XOR-Eigenschaften“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser DSA Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede DSA Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Bitweise Operatoren: AND, OR, XOR, NOT und Verschiebungen
- Single Number und XOR-Eigenschaften
- Bitmasken: Setzen, Löschen, Umschalten und Prüfen
- Bits zählen, fehlende Zahl und Bits umkehren