XOR techniques

XOR has four properties: a ^ a = 0, a ^ 0 = a, it is commutative (a ^ b = b ^ a) and associative. Together they mean that in a long chain of XORs, every value that appears twice cancels, whatever the order.

So x ^ y ^ x = y. The next lessons build on this: XOR everything and only the values with odd multiplicity survive.

In an array where every value appears twice except one, XOR all elements. The pairs cancel to 0 and the unique value remains. The animation shows the running XOR in binary: each repeated value flips its bits back.

Time is O(n) and space O(1). A hash map or sort would work too, but needs O(n) extra space or O(n log n) time.

1static int findUnique(int[] a) {
2    int x = 0;
3    for (int v : a) x ^= v;
4    return x;
5}

1static int findUnique(int[] a) {
2    int x = 0;
3    for (int v : a) {
4        x ^= v;                  // equal pairs cancel: v ^ v == 0
5    }
6    return x;
7}

Given n distinct numbers taken from 0..n, one number is missing. XOR the indices 0..n-1 and the value n together with all the array values. Every number present appears twice (once as an index or n, once as a value) and cancels, leaving the missing one. Try the “Missing 0” and “Missing n” presets.

The sum formula n(n + 1)/2 - sum also works, but the sum can overflow int for large n. XOR cannot overflow.

1static int missing(int[] a) {          // a holds 0..n except one value
2    int x = a.length;                    // start with n
3    for (int i = 0; i < a.length; i++) {
4        x ^= i ^ a[i];                   // XOR in index and value
5    }
6    return x;
7}

If every value appears three times except one, plain XOR fails (three copies do not cancel). Instead count, for each bit position, how many numbers have that bit set, modulo 3. The bits that remain make up the unique number.

If two values appear once and the rest twice, XOR everything to get a ^ b. Any set bit of that result separates a from b. Use the lowest one to split the array into two groups, and XOR each group to recover a and b.

1// every number appears 3 times except one
2static int singleOfThree(int[] a) {
3    int result = 0;
4    for (int bit = 0; bit < 32; bit++) {
5        int count = 0;
6        for (int v : a) count += (v >> bit) & 1;
7        if (count % 3 != 0) result |= 1 << bit;
8    }
9    return result;
10}
11
12// two numbers appear once, all others twice
13static int[] twoSingles(int[] a) {
14    int xor = 0;
15    for (int v : a) xor ^= v;              // a ^ b
16    int lowest = xor & -xor;               // a bit where a and b differ
17    int x = 0, y = 0;
18    for (int v : a) {
19        if ((v & lowest) != 0) x ^= v; else y ^= v;
20    }
21    return new int[] { x, y };
22}

As with sums, define prefix[i] = a[0] ^ … ^ a[i-1]. Then the XOR of any range is prefix[r + 1] ^ prefix[l], because the shared prefix cancels. Range XOR queries take O(1) after an O(n) build.

It also solves counting problems: the number of subarrays with XOR equal to k is the number of pairs of prefixes whose XOR is k, found with a hash map of prefix values.

1static int[] buildPrefixXor(int[] a) {
2    int[] p = new int[a.length + 1];
3    for (int i = 0; i < a.length; i++) p[i + 1] = p[i] ^ a[i];
4    return p;
5}
6static int rangeXor(int[] p, int l, int r) { return p[r + 1] ^ p[l]; }   // inclusive l..r
7
8// count subarrays whose XOR is k
9static int countXorK(int[] a, int k) {
10    Map<Integer, Integer> seen = new HashMap<>();
11    seen.put(0, 1);
12    int prefix = 0, count = 0;
13    for (int v : a) {
14        prefix ^= v;
15        count += seen.getOrDefault(prefix ^ k, 0);   // an earlier prefix p with p ^ prefix == k
16        seen.merge(prefix, 1, Integer::sum);
17    }
18    return count;
19}

The XOR swap, a ^= b; b ^= a; a ^= b;, exchanges two variables without a temporary. It is a well-known trick but a poor choice: it is not faster than a temporary on modern CPUs and compilers, and it is harder to read.

It also has a real bug: if both operands refer to the same location, for example swapping arr[i] with arr[j] when i == j, the first step sets that value to x ^ x = 0, and the value is lost.

1static void xorSwap(int[] arr, int i, int j) {
2    arr[i] ^= arr[j];
3    arr[j] ^= arr[i];
4    arr[i] ^= arr[j];
5}
6int[] a = {7, 8};
7xorSwap(a, 0, 1);      // [8, 7]  works
8xorSwap(a, 1, 1);      // [8, 0]  the element was zeroed, because i == j
9
10static void swap(int[] arr, int i, int j) { int t = arr[i]; arr[i] = arr[j]; arr[j] = t; }   // prefer this