XOR Deep Dive

XOR Deep Dive

Of the bitwise operators, XOR (^) is the one interviewers reach for again and again, because it has an algebra that lets numbers cancel. Where AND and OR lose information (you cannot undo an OR), XOR is perfectly reversible — and that reversibility is the single property behind Single Number, Missing Number, swap-without-a-temp, and finding a duplicate. Learn the algebra once and those problems stop being tricks and become the same idea wearing different clothes.

Bit by bit, a ^ b is 1 exactly when the two bits differ — it is addition modulo 2 with no carry:

Two readings of that table are worth holding in your head: XOR is a "controlled flip" (XOR-ing with 1 flips a bit, with 0 leaves it) and a "difference detector" (the result marks precisely the bit positions where a and b disagree).

The algebra — four laws, each provable from the table

• Identity: a ^ 0 = a. Every bit of a is XOR-ed with 0, and the table says b ^ 0 = b — nothing changes. 0 is the "do nothing" element.
• Self-inverse: a ^ a = 0. Every bit is XOR-ed with itself; equal bits give 0. Every value is its own inverse — XOR-ing a number in and then in again returns you to the start.
• Commutative: a ^ b = b ^ a. The truth table is symmetric in a and b. Order does not matter.
• Associative: (a ^ b) ^ c = a ^ (b ^ c). Per bit it is addition mod 2, which is associative. Grouping does not matter.

Commutativity + associativity together mean you can XOR a whole list in any order and any grouping and get the same answer. Combine that with self-inverse and identity and you get the property that does all the work:

The cancellation property — the engine

XOR-ing a long list, any value that appears an even number of times contributes 0, and any value that appears an odd number of times contributes itself. Proof: because order is free, mentally group all equal values together. A value appearing twice is v ^ v = 0 (self-inverse); appearing four times is (v^v)^(v^v) = 0; any even count folds to 0. An odd count is those pairs (0) plus one leftover v, and 0 ^ v = v (identity). So after XOR-ing everything, only the odd-count values survive — and if exactly one value is unpaired, XOR hands it straight to you.

Traced example — a pile cancelling to the lone value

Array [4, 1, 2, 1, 2] — every value appears twice except 4. XOR them left to right into an accumulator acc (start at 0):

The accumulator wanders—4, 5, 7, 6—then lands back on 4. The cancellation view makes it obvious why, independent of the wandering: reorder the XOR as 4 ^ (1 ^ 1) ^ (2 ^ 2) = 4 ^ 0 ^ 0 = 4. The pairs annihilate; the loner remains.

Where this shows up

Missing Number, traced on [3, 0, 1] (values from 0..3, so 2 is missing). Seed acc = n = 3, then fold in i ^ nums[i]:

Indices contributed {3, 0, 1, 2} (the seed 3 plus loop indices 0,1,2) and values contributed {3, 0, 1}. Every number in both sets cancels; 2 appears only as an index → it is the answer.

Java: cancellation in action

import java.util.Arrays;

public class Xor {

    // Every value appears twice except one — XOR leaves the loner.
    static int singleNumber(int[] nums) {
        int acc = 0;
        for (int v : nums) acc ^= v;      // pairs cancel to 0
        return acc;
    }

    // The missing value in 0..n: XOR indices against values.
    static int missingNumber(int[] nums) {
        int acc = nums.length;            // seed with n, the index that has no slot
        for (int i = 0; i < nums.length; i++) acc ^= i ^ nums[i];
        return acc;
    }

    public static void main(String[] args) {
        System.out.println(singleNumber(new int[]{4, 1, 2, 1, 2})); // 4
        System.out.println(missingNumber(new int[]{3, 0, 1}));      // 2

        // XOR swap, traced: 5 and 9.
        int x = 5, y = 9;
        x = x ^ y;   // x = 12
        y = x ^ y;   // y = 5
        x = x ^ y;   // x = 9
        System.out.println("x=" + x + " y=" + y);                   // x=9 y=5

        // The aliasing trap: xor-swapping a slot with ITSELF zeroes it.
        int[] arr = {7, 8};
        int i = 0, j = 0;                 // same index
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
        System.out.println(Arrays.toString(arr));                   // [0, 8]  — 7 destroyed!
    }
}

Go: cancellation in action

package main

import "fmt"

// Every value appears twice except one — XOR leaves the loner.
func singleNumber(nums []int) int {
	acc := 0
	for _, v := range nums {
		acc ^= v // pairs cancel to 0
	}
	return acc
}

// The missing value in 0..n: XOR indices against values.
func missingNumber(nums []int) int {
	acc := len(nums) // seed with n, the index that has no slot
	for i, v := range nums {
		acc ^= i ^ v
	}
	return acc
}

func main() {
	fmt.Println(singleNumber([]int{4, 1, 2, 1, 2})) // 4
	fmt.Println(missingNumber([]int{3, 0, 1}))      // 2

	// XOR swap, traced: 5 and 9.
	x, y := 5, 9
	x = x ^ y // x = 12
	y = x ^ y // y = 5
	x = x ^ y // x = 9
	fmt.Printf("x=%d y=%d\n", x, y) // x=9 y=5

	// The aliasing trap: xor-swapping a slot with ITSELF zeroes it.
	arr := []int{7, 8}
	i, j := 0, 0 // same index
	arr[i] = arr[i] ^ arr[j]
	arr[j] = arr[i] ^ arr[j]
	arr[i] = arr[i] ^ arr[j]
	fmt.Println(arr) // [0 8]  — 7 destroyed!
}

The XOR swap — a party trick, not production code

The three-line swap works because XOR is reversible. Trace x=5, y=9: after x = x^y, x holds the "difference" 5^9 = 12; then y = x^y = (5^9)^9 = 5 (the second 9 cancels), and x = x^y = (5^9)^5 = 9. Values exchanged, no temporary. Cute. Do not use it in real code, for three concrete reasons:

• It is broken under aliasing. If both operands are the same memory location — swap(arr[i], arr[j]) with i == j — the first step is a = a ^ a = 0, which zeroes the location, and the original value is gone forever. The trace above shows [7, 8] becoming [0, 8]. A plain temp-variable swap is immune.
• It is not faster. On any modern CPU, a temp-variable swap is register moves the compiler already optimizes (often to a single XCHG or just register renaming). The XOR version adds a data dependency chain — each step needs the previous result — which can be slower than three independent moves. The "saves memory" claim is a myth from an era of register scarcity.
• It destroys readability. A reviewer must trace three XORs to conclude "this swaps two things", which tmp = a; a = b; b = tmp; says at a glance.

Know it so you can explain why it works (it proves you understand reversibility) and, more importantly, why you would never ship it.

Traps

• XOR needs the "each duplicate an even number of times" guarantee. Single Number is only solvable by XOR because every other element appears exactly twice. If some element could appear three times (Single Number II), plain XOR fails — a value XOR-ed in thrice equals itself, not 0, so it does not cancel. Different problem, different technique (bit-count mod 3).
• Missing Number by XOR vs by sum. The sum formula n(n+1)/2 - ∑nums also works and is a one-liner, but the running sum can overflow for large n in a fixed-width int. XOR never overflows — it stays inside the word — so it is the safer choice when values are large.
• Signedness is irrelevant to XOR itself. XOR is a pure bit operation; it treats the sign bit like any other and never triggers Java's arithmetic-shift surprises. That is part of why it is so clean.
• Accumulator must start at the identity, 0. Seeding an XOR fold with anything other than 0 (unless you mean to, as in Missing Number where we deliberately seed with n) corrupts the result.

When to reach for XOR — and when not

• vs. a hash set (Single Number). A HashSet that adds/removes each value also finds the loner in O(n) time, but costs O(n) space; XOR is O(n) time and O(1) space. In an interview, lead with the XOR answer when the "everything pairs up" structure is explicit — it signals you see the algebra. But if the constraints differ (elements appear a variable number of times, or you also need the counts), the hash map is the correct, general answer — do not force XOR where the pairing guarantee does not hold.
• vs. the sum formula (Missing Number). Both are O(n)/O(1). Choose XOR when overflow is a risk or the interviewer bans arithmetic; choose sum when it reads more clearly and values are safely small.
• vs. sorting. Sorting to find a unique or missing element is O(n log n) and mutates input; XOR is O(n), read-only, and O(1) space. Sorting only wins if the array is already sorted or you need order for another reason.

Takeaways

• XOR is addition mod 2 per bit: 1 where bits differ. Its four laws (identity a^0=a, self-inverse a^a=0, commutative, associative) are all read straight off the truth table.
• The engine is cancellation: XOR a list and even-count values vanish, odd-count values survive — independent of order.
• That one property drives Single Number, Missing Number (overflow-free, unlike the sum trick), and the split step of Single Number III.
• The XOR swap is a reversibility demo, not production code — it breaks under aliasing, is not faster, and hides intent. Prefer XOR over a hash set only when the "pairs up" guarantee genuinely holds.