XOR tricks
In one line
Because x ^ x = 0 and x ^ 0 = x, XOR-ing a list makes every pair cancel out, which finds unique or missing values in O(n) time and O(1) space.
What it is
XOR (exclusive or) returns 1 for a bit position when the two input bits differ and 0 when they are the same. For whole integers it works on every bit at once: 5 ^ 3 is 101 ^ 011 = 110 = 6.
Four properties make XOR special. Anything XOR itself is 0. Anything XOR 0 is itself. Order does not matter (it is commutative and associative). And it undoes itself: if c = a ^ b then c ^ b = a. Together these mean that in a long chain of XORs, every value that appears an even number of times disappears.
Why interviewers ask
XOR questions such as Single Number and Missing Number are favourites because the obvious answer uses a hash set (O(n) space) and the XOR answer uses O(1) space. They test whether you can reason about algebraic properties, and the harder versions (two unique numbers) test whether you can combine XOR with isolating a bit.
How it works
- 1Start an accumulator at 0, because 0 is the neutral value for XOR.
- 2XOR every element into the accumulator. Order does not matter, so you can imagine grouping equal values together.
- 3Each pair of equal values becomes 0, and 0 changes nothing, so only the values that appear an odd number of times remain.
- 4For a missing number in 0..n, XOR all indices 0..n and all values together; every present number appears twice and cancels, leaving the missing one.
- 5For two unique values a and b, the total XOR is a ^ b. Any set bit in it is a position where a and b differ. Split the numbers into two groups by that bit and XOR each group separately to recover a and b.
Worked example · Finding the single number in [4, 1, 2, 1, 2]
- acc = 0.
- acc ^= 4: 000 ^ 100 = 100, so acc = 4.
- acc ^= 1: 100 ^ 001 = 101, so acc = 5.
- acc ^= 2: 101 ^ 010 = 111, so acc = 7.
- acc ^= 1: 111 ^ 001 = 110, so acc = 6. The first 1 has now cancelled.
- acc ^= 2: 110 ^ 010 = 100, so acc = 4. The 2s have cancelled too, leaving the answer 4.
Picture it
XOR is like a light switch toggle. Every time a number appears, it flips its pattern of lights. Flip something twice and it is back to off, so after all the flips the only lights still on belong to the number that appeared once.
Reference code
def single_number(nums):
# every value appears twice except one: pairs cancel out
acc = 0
for x in nums:
acc ^= x
return acc
def missing_number(nums):
# nums holds 0..n with one value missing
acc = len(nums)
for i, x in enumerate(nums):
acc ^= i ^ x
return acc
def two_singles(nums):
# every value appears twice except two different values a and b
both = 0
for x in nums:
both ^= x # both = a ^ b, non-zero
low = both & -both # lowest bit where a and b differ
a = 0
for x in nums:
if x & low: # split into two groups by that bit
a ^= x
return a, both ^ a
print(single_number([4, 1, 2, 1, 2])) # 4
print(missing_number([3, 0, 1])) # 2
print(two_singles([1, 2, 1, 3, 2, 5])) # (3, 5) or (5, 3)
single_number and missing_number are one pass with one accumulator. two_singles does two passes: the first finds a ^ b, then x & -x keeps only its lowest set bit, which a and b disagree on, so they land in different groups.
Key patterns
Pairs cancel (Single Number)
When: Every value appears twice except one
How: XOR all values; the result is the unique one. O(n) time, O(1) space.
Missing number
When: Array holds 0..n with one value missing
How: XOR all indices 0..n and all values; the present ones cancel. This also avoids the overflow risk of the sum formula in fixed-width languages.
Two unique values
When: Every value appears twice except two
How: x = a ^ b, isolate its lowest set bit with x & -x, split the array by that bit, and XOR each group.
Undo with the same key
When: Encoding and decoding, or swapping
How: c = a ^ k encodes and c ^ k decodes. The XOR swap (a ^= b; b ^= a; a ^= b) works but fails if a and b are the same memory location, so prefer a temp variable.
Real-world use
RAID 5 parity
RAID 5 stores the XOR of the data blocks on the other disks as a parity block. If one disk dies, XOR-ing the parity with the surviving blocks rebuilds every lost block, because the survivors cancel out.
Stream ciphers and one-time pads
ChaCha20 and AES in CTR mode produce a keystream and XOR it with the plaintext. The receiver XORs the same keystream again to get the plaintext back, using the fact that XOR undoes itself.
Zobrist hashing in chess engines
Engines such as Stockfish give each piece-on-square a random 64-bit number and hash a position as the XOR of them. Moving a piece updates the hash with two XORs instead of recomputing it from scratch.
Simple checksums
Many serial and embedded protocols, such as NMEA sentences from GPS receivers, use an XOR of all bytes as a checksum, so a single flipped bit changes the result.
In a project
A data pipeline copies 50 million order IDs from a primary database to a warehouse every night, and you need a fast check that exactly one ID went missing or was duplicated, without loading all IDs into memory.
- While streaming rows from the source, keep a running XOR of all order IDs (and a count).
- Do the same while streaming the destination table.
- If the counts and XORs match, the sets very likely match. If exactly one ID is missing, source XOR destination equals that ID.
- Back the XOR check with a stronger hash for production, since different sets can produce the same XOR.
Impact: The check uses O(1) memory and one streaming pass over each side, so it runs in minutes on a small worker instead of needing a large join, and in the single-missing case it names the exact lost record.
Trade-offs
Use it when
- Every element appears an even number of times except the ones you want
- You must use O(1) extra space
- You need a reversible operation with the same key
Avoid it when
- Values can appear an odd number of times (other than the target), such as three times each; use per-bit counting modulo 3 instead
- You need to detect any difference between two large sets reliably; XOR collisions are easy, so use a real hash
- Readability matters more than saving one variable, such as the XOR swap in production code
Cost: One pass: O(n) time and O(1) space. Two unique values: two passes, still O(n) time and O(1) space.
Common mistakes
- Starting the accumulator at the first element and then XOR-ing it again, which cancels it.
- Applying the pair-cancelling trick when duplicates appear three times; XOR only cancels even counts.
- In two_singles, splitting by a bit that is not set in a ^ b, so both unique values land in the same group.
- Claiming the XOR swap is faster; modern compilers make a temp swap just as fast, and XOR swap zeroes a value when both names point to the same location.
- Forgetting that in Python, x & -x works for positive x but needs care with negative inputs.
Interview questions
Quick revision
- x ^ x = 0, x ^ 0 = x, XOR is commutative and associative.
- XOR of a list leaves values that appear an odd number of times.
- If c = a ^ b then c ^ b = a: XOR undoes itself.
- x & -x isolates the lowest set bit.
- Missing number: XOR indices 0..n with all values.
- Two singles: split by a bit set in a ^ b.
- Three-times variant: count bits mod 3 instead.
Check yourself
1. What is 5 ^ 7 ^ 5?
2. Using XOR, what is the missing number in [3, 0, 1]?
3. What does 12 & -12 return?
4. Why does plain XOR fail when every other value appears three times?
Related
Saved on this device. Create a free account to keep it on every device.
Practise this with Sam
A real mock interview, out loud, with an honest scorecard. Free to start.