Short notes on mathematics and programming

Short notes on mathematics and programming

xor_inv

Proof of XOR swap

Cheat sheet
✍️ XOR toggles bits: a ^ b ^ b = a
✍️ Step-by-step proof for a0, b0
✍️ Swap without a temporary variable always works correctly

Lecture
In the previous note we showed XOR swap with examples and a table. A demonstration is not a proof. Below is a short strict explanation of why XOR swap works.

Think of a ^ b as toggling (inverting) bits of a in positions where b has 1s. Toggle twice and you get the original value back: a ^ b ^ b = a.

// Let initial values be a0 and b0
let a = a0, b = b0;
a = a ^ b;      // a = a0 ^ b0,        b = b0
b = a ^ b;      // a = a0 ^ b0,        b = b0 ^ (a0 ^ b0) = a0
a = a ^ b;      // a = a0 ^ b0 ^ a0 = b0, b = a0

General result: values are swapped without a temporary variable for any integer a0 and b0.

#education #devTopic #junior