AlgoScope

XOR Tricks

algorithmintermediateTime O(n)Space O(1)

XOR is addition without carries, so it forgets nothing and cancels perfectly: x xor x = 0, x xor 0 = x, and the order never matters. Fold a whole array into one number and every pair erases itself, leaving only what was unpaired.

6091

Swap a = 6 and b = 9 with three XORs and no temporary. The trick is that after the first step a holds both values mixed together, and either one can be recovered by XORing the other.

Check your understanding

The player pauses before the one decision in this run and asks what happens next. Here it is, with the answer.

  1. a is now 6 xor 9 = 15. What does b = a xor b give?

    • 6
    • 9
    • 15

    Answer: 6. (6 xor 9) xor 9 = 6. The b cancels out and the original a is left.

How it runs, step by step

  1. Swap a = 6 and b = 9 with three XORs and no temporary. The trick is that after the first step a holds both values mixed together, and either one can be recovered by XORing the other.

    Swapping 6 and 9 with three XOR operations.

  2. a = a xor b = 6 xor 9 = 15. Neither original is visible now, but both are in there.

    a becomes 15, the XOR of both values.

  3. b = a xor b = 15 xor 9 = 6. That is the original a: (6 xor 9) xor 9 leaves 6, because the 9 cancels itself.

    b becomes 6, which is the original a.

  4. a = a xor b = 15 xor 6 = 9. That is the original b: (6 xor 9) xor 6 leaves 9.

    a becomes 9, which is the original b.

  5. Swapped: a = 9, b = 6. Three XORs, no temporary. Neat, but a plain temp is clearer in real code.

    The values are swapped. a is 9 and b is 6.

Write it yourself

Define singleNumber(values) and return the one value that appears once, where every other appears twice. It runs in your browser against this lesson's own 2 examples.

// Exclusive-or the whole array. Every pair cancels to zero and the odd one out is what is left.function singleNumber(values) {    return 0;}
Ln 1, Col 16 linesTab indents; Escape then Tab leaves the editor. Ctrl-Enter runs, Cmd-Enter on a Mac.

Remember

  • x xor x = 0 and x xor 0 = x. Commutative and associative, so pairs cancel wherever they sit.
  • Single number: XOR everything. Missing number: XOR what should be there against what is.
  • The XOR swap works, but a temporary variable is clearer and no slower. Know the trick, do not ship it.

Topics covered

Related

Where this is used

StorageRAID 5 parity

A RAID 5 stripe stores the XOR of its data blocks as a parity block. When a drive dies the lost block is rebuilt by XOR-ing the survivors with that parity, which is the single-number fold exactly: every block still present cancels out and only the absent one remains. RAID 6 and Reed-Solomon erasure codes add more parity blocks, but XOR is still the addition they are built on.

CryptographyStream ciphers

ChaCha20, the cipher TLS 1.3 clients pick when the CPU has no AES acceleration and the only data cipher WireGuard offers, encrypts by XOR-ing plaintext with a keystream derived from the key. Decryption is the identical operation, because XOR-ing with the same keystream twice gives the original bytes back, so there is one code path instead of two. The same property is why reusing a keystream is fatal: XOR the two ciphertexts together and the key cancels, leaving the two plaintexts folded onto each other.

GamesZobrist hashing in chess engines

Stockfish identifies a board position by a 64-bit key built as the XOR of random numbers, one per piece-and-square combination. Making a move XORs out the key for the piece's old square and XORs in the key for its new one, so the position hash updates in two operations rather than rehashing 64 squares. Unmaking the move XORs those same two keys back, because each key is its own undo - which is what makes a transposition table cheap enough to consult at every node.

Language runtimesXorshift generators

V8, the JavaScript engine in Chrome and Node.js, has produced Math.random values with xorshift128+ since 2015, and its whole step is XOR-ing the state with shifted copies of itself. XOR with a shift is reversible, so the state can never lose information and collapse into a short cycle. The state update needs no multiply and no modulus, only shifts and XORs, which is what keeps it cheap enough to sit behind every Math.random call.

Why it works this way

Why not just add everything up?

For the missing number a running sum works too, but it needs the expected total as a second ingredient and a subtraction to undo it, and that total overflows a 32-bit integer once n passes about 65,000. XOR carries nothing between bit columns, so it cannot overflow, and it is its own inverse, so the same fold both builds and cancels. For the single number addition fails outright: x + x is 2x, not 0, so nothing ever cancels.

The XOR swap destroys the value when i equals j

swap(a, i, i) starts with a[i] = a[i] xor a[i], which is zero, and the two lines after it have nothing left to recover. Sorting and partition loops swap an element with itself all the time, which is exactly how this bug reaches production, and the same failure hits any two arguments that alias the same memory. The three XORs also form a dependency chain the CPU must execute in order, while a temporary-variable swap is usually just register renaming the CPU never issues as work.

It finds one unpaired number, not two

The fold isolates a value only when every other value appears an even number of times. With two unpaired numbers you get their XOR instead, so take any bit that is 1 in that result - the lowest set bit is easiest to extract - and split the array into values with that bit set and values without: the two unpaired numbers must land in different halves, and one more fold per half finds each. Triples are a different problem, because XOR counts each bit column modulo 2 and a value appearing three times leaves its bits behind; there you count each column modulo 3 instead.

The missing-number loop runs to n, not n - 1

The array holds n values drawn from 0 through n with one gap, so there are n + 1 candidates for only n slots, and i must reach a.size rather than a.size - 1. Getting this wrong does not crash: you fold in one number too few and quietly return the wrong answer. The assumption underneath it is just as load-bearing - if the values are not exactly the range 0..n, there is nothing for the fold to cancel against and the result means nothing.

Read more

Next up