Swapping Two Values with XOR

XOR Swap Algorithm

The XOR swap exchanges two variables without using a temporary variable:

a = a ^ b;
b = a ^ b;  // b now has original a
a = a ^ b;  // a now has original b

Step-by-Step Walkthrough

Let a = 42 (00101010) and b = 15 (00001111):

Step 1: a = a ^ b

  00101010
^ 00001111
──────────
  00100101  (a = 37)

Step 2: b = a ^ b (using new a)

  00100101  (a = 37)
^ 00001111  (b = 15)
──────────
  00101010  (b = 42, original a!)

Step 3: a = a ^ b (using new b)

  00100101  (a = 37)
^ 00101010  (b = 42)
──────────
  00001111  (a = 15, original b!)

Why It Works

The three XOR operations encode and decode values using XOR's self-inverse property. After step 1, a holds a ^ b. Step 2 computes (a ^ b) ^ b = a (recovering original a into b). Step 3 computes (a ^ b) ^ a = b (recovering original b into a).

Limitations and Caveats

1. Same variable: If a and b refer to the same memory location (e.g., same array index), XOR swap zeroes the value because x ^ x = 0.

2. Performance: On modern CPUs with register renaming and out-of-order execution, the XOR swap is actually slower than using a temporary variable because each step depends on the previous result, creating a pipeline dependency chain.

3. Readability: A simple [a, b] = [b, a] in JavaScript or std::swap in C++ is clearer and equally fast.

When It's Useful

The XOR swap is mainly useful in extremely memory-constrained environments (embedded systems with no stack space) or as an educational example of XOR's properties.