XOR TricksXOR tricks

01Why it exists

Reach for it when you see:Everything pairs up except one, two lists differ by a single entry, one number missing from 0 to n, appears an odd number of times, O(1) extra space required, parity checks, one operation that both encrypts and decrypts, swapping without a temporary.

02The core idea

XOR (exclusive or) yields 1 where two bits differ and 0 where they agree, which is another way of saying it is binary addition without carries: add each bit position on its own, then take the result mod 2. From that angle, four properties fall out naturally: a ^ 0 = a (adding 0 changes nothing), a ^ a = 0 (every position is 0+0 or 1+1, and both are 0 mod 2), plus the commutativity and associativity that addition already has. The first two together say that XOR is its own inverse: XORing by the same value twice is the same as doing nothing at all. Every trick in this lesson follows from that one sentence.

XOR a whole list of numbers together and bit k of the result tells you whether the number of 1s in bit k across the list is odd or even. So values that appear an even number of times disappear completely, and values that appear an odd number of times survive — and the order is irrelevant, because commutativity and associativity let you group equal values together and cancel them in pairs first. In Single Number every other value appears twice, so XORing everything leaves the odd one out. Missing Number throws the expected 0..n in with the array's own values: the numbers that are present appear twice each, and the missing one appears just once. If there are two unpaired values a and b, the total XOR is a ^ b, which is non-zero because a ≠ b. Pull out its lowest set bit (diff & -diff), and a and b are guaranteed to differ on that bit. Split the whole list on it: equal values agree on that bit and always land in the same group, while a and b land in different ones. Each group is then a Single Number problem of its own. The swap is the same property once more: a ^= b parks a ^ b in a, b ^= a gives b ^ a ^ b = a, and a ^= b then gives a ^ b ^ a = b.

Each value is XORed exactly once, so the time is O(n), and since you have to see the whole input before the answer is known, the best and worst cases are identical; one accumulator is all you keep, so the space is O(1). The two-unpaired-values version scans twice and is still O(n) and O(1). Compare that with the intuitive approaches: a hash set recording which values you have seen is O(n) time but O(n) space, and sorting first to look for the unpaired value is O(n log n). XOR also cannot overflow: summing to find a missing number already exceeds a 32-bit integer at n = 10⁵. For repeated range-XOR queries the recipe is the same as a prefix sum — P[i+1] = P[i] ^ nums[i], and the XOR of nums[l..r] is P[r+1] ^ P[l], O(n) time and space to build and O(1) per query. A prefix sum subtracts to strip off the leading part; XOR is its own inverse, so you simply XOR once more.

A few common traps. First, XOR only distinguishes odd counts from even counts: if the other values each appear three times (Single Number II), three is odd, XOR cancels nothing, and you need per-bit counts of 1s taken mod 3 instead. Second, operator precedence: in C++ == binds tighter than ^ and &, so a ^ b == 0 actually means a ^ (b == 0) and the parentheses are mandatory; in Python the bitwise operators bind tighter, so the trap never arises. Third, the XOR swap clears the value to 0 on its very first step when both references point at the same variable (swapping nums[i] with nums[j] when i == j, say); modern compilers optimise the temporary-variable swap thoroughly, so the XOR swap is worth knowing for the insight into cancellation rather than for speed. Fourth, computing -diff on a C++ int overflows when diff is INT_MIN, so use unsigned. How this sits next to its neighbours: Bitwise Basics uses XOR to flip selected bits, whereas here it is used to cancel them; and the next lesson, Counting Bits, computes Hamming distance by using a ^ b to expose the differing bits before counting the 1s.

03The algorithm

1. 1Restate the problem in terms of parity: "the answer appears an odd number of times, every other value appears an even number of times". Everything pairing up except one, two lists differing by a single element, and a gap in 0..n all rewrite this way.
2. 2Start with acc = 0 and fold in every relevant value with acc ^= x. For missing-number problems, feed in what should be there as well: XOR each index 0..n-1 and n exactly once.
3. 3When the scan finishes, acc is the answer. No sorting, no record of what you have already seen, and neither the input order nor the sign of the values changes the result.
4. 4With two unpaired values, acc comes out as a ^ b. Take low = acc & -acc, scan again XORing only the values where x & low is non-zero, and that gives you one of them, a; the other is acc ^ a.
5. 5For repeated range-XOR queries, build the prefix P[i+1] = P[i] ^ nums[i]; the answer for [l, r] is P[r+1] ^ P[l]. In C++, parenthesise any XOR or AND that shares an expression with a comparison operator.

04Interactive demo

The first half is Single Number: nums = [5, 3, 9, 3, 5, 12, 9]. Each step XORs one value into acc, and the rows underneath show the acc before the step, the value, and the result in 4-bit binary. In the array on top, blue is the value being processed, amber marks values already XORed in that are still waiting for their partner, and grey marks a pair that has cancelled. Notice what happens the second time a value appears: it flips back exactly the bits it flipped the first time, as if it had never arrived at all. After all seven values, only 12 remains. The second half runs the three-line XOR swap with a = 5 and b = 9; blue is the line executing, finished lines turn grey, and the variable just overwritten is highlighted in amber, so you can watch the intermediate a ^ b = 12 hold both numbers at once.

05Code

Three functions: Single Number itself, Missing Number pairing each index against its value, and the two-unpaired-values version that splits on the lowest set bit — then a demonstration of the XOR swap. The C++ swap first checks whether the two references point at the same variable, and it switches to unsigned when isolating the lowest set bit to sidestep the overflow of negating INT_MIN.

def single_number(nums):
    """Every other value appears twice; find the one that appears once. O(n) time, O(1) space"""
    acc = 0
    for x in nums:
        acc ^= x                  # pairs cancel each other out: x ^ x = 0
    return acc                    # what is left is the odd one out: 0 ^ a = a


def missing_number(nums):
    """nums holds 0..n with one value missing (length n); find the missing one"""
    acc = len(nums)               # n has no matching index, so seed it in first
    for i, x in enumerate(nums):
        acc ^= i ^ x              # XOR in the expected i and the actual x
    return acc                    # present values appear twice and cancel; the gap remains


def two_single_numbers(nums):
    """Exactly two values a != b appear once; every other value appears twice"""
    diff = single_number(nums)    # pairs cancel, leaving a ^ b, which is never 0
    low = diff & -diff            # lowest set bit: a and b differ on this bit
    a = 0
    for x in nums:
        if x & low:               # split on that bit; equal values always land together
            a ^= x                # a is the only unpaired value in this group
    return sorted([a, diff ^ a])  # the other one is (a ^ b) ^ a = b


if __name__ == "__main__":
    print(single_number([5, 3, 9, 3, 5, 12, 9]))         # 12 (same values as the demo)
    print(missing_number([3, 0, 1]))                     # 2
    print(missing_number([9, 6, 4, 2, 3, 5, 7, 0, 1]))   # 8
    print(two_single_numbers([1, 2, 1, 3, 2, 5]))        # [3, 5]
    print(two_single_numbers([-4, 7, 7, 6]))             # [-4, 6] (negatives work too)

    a, b = 5, 9                   # swap with no temporary (Python would normally write a, b = b, a)
    a ^= b                        # a = 5 ^ 9 = 12
    b ^= a                        # b = 9 ^ 12 = 5
    a ^= b                        # a = 12 ^ 5 = 9
    print(a, b)                   # 9 5

06Practice

• LeetCode 136Single NumberEasy
• LeetCode 268Missing Number (XOR the indices and the values together)Easy
• LeetCode 389Find the Difference (characters XOR too)Easy
• LeetCode 1310XOR Queries of a Subarray (prefix XOR)Medium
• LeetCode 260Single Number III (split on the lowest set bit)Medium
• LeetCode 137Single Number II (XOR fails at three copies; count bits instead)Medium