XOR Tricks

The Idea

XOR has two properties that do all the work: x ^ x is 0, and x ^ 0 is x. It also ignores order.

So XOR a whole list together and every value that appears twice erases itself. Whatever survives appeared an odd number of times — in O(n) time and O(1) memory.

Real-World Example

RAID 5 stores one parity drive that is the XOR of the others. Lose any single disk and its contents are rebuilt by XOR-ing everything that remains: the missing block is the value that no longer has a partner.

The Code

def single_number(nums):
    acc = 0
    for x in nums:     # x ^ x == 0, and order does not matter
        acc ^= x
    return acc         # every pair cancels; the loner survives

print(single_number([4, 1, 2, 1, 2]))   # 4
print(7 ^ 7, 7 ^ 0)                     # 0 7

a, b = 3, 9
a ^= b         # a holds the difference of the two
b ^= a         # ...so b recovers the old a
a ^= b         # ...and a recovers the old b
print(a, b)    # 9 3

def single_number(nums):
  acc = 0
  for x in nums:
      acc = acc ___ x
  return acc

print(single_number([9, 5, 9]))   # want 5