Swap Variables Without Temporary Memory Using XOR

This article explains how to use the bitwise XOR (Exclusive OR) operator to swap the values of two variables without allocating any temporary memory or intermediate variables. By understanding the core mathematical and binary properties of the XOR operation—namely self-inversion, commutativity, and associativity—you can execute an in-place swap using three straightforward operations.

Core Properties of Bitwise XOR

The XOR operation processes data at the binary bit level. For each bit position, it outputs 1 if the bits are different and 0 if they are identical. The XOR swap algorithm relies on three fundamental mathematical properties:

  1. Identity: \(X \oplus 0 = X\) (Any number XORed with zero remains unchanged)
  2. Self-Inverse: \(X \oplus X = 0\) (Any number XORed with itself yields zero)
  3. Commutativity and Associativity: \(A \oplus B = B \oplus A\) and \((A \oplus B) \oplus C = A \oplus (B \oplus C)\) (The order of operations does not affect the result)

The Three-Step Swap Algorithm

To swap two variables, A and B, you execute three sequential XOR operations:

1. A = A ^ B
2. B = A ^ B
3. A = A ^ B

Algebraic Proof

  1. A = A ^ B: A now stores the combined bit pattern (\(A \oplus B\)), while B retains its original value.
  2. B = A ^ B: Substitute the new value of A into the equation: \[\text{New } B = (A \oplus B) \oplus B = A \oplus (B \oplus B) = A \oplus 0 = A\] Variable B now holds the original value of A.
  3. A = A ^ B: Substitute the current values of A (\(A \oplus B\)) and B (which is now original \(A\)): \[\text{New } A = (A \oplus B) \oplus A = (A \oplus A) \oplus B = 0 \oplus B = B\] Variable A now holds the original value of B.

Step-by-Step Binary Example

Assume variable A = 5 and variable B = 9. In 4-bit binary representation: * \(A = 0101_2\) * \(B = 1001_2\)

Step 1: A = A ^ B

  0101 (A)
^ 1001 (B)
-------
  1100 (New A)

A becomes 1100 (\(12\)), B remains 1001 (\(9\)).

Step 2: B = A ^ B

  1100 (Current A)
^ 1001 (Current B)
-------
  0101 (New B)

B becomes 0101 (\(5\), the original value of A).

Step 3: A = A ^ B

  1100 (Current A)
^ 0101 (Current B)
-------
  1001 (New A)

A becomes 1001 (\(9\), the original value of B).

The swap is complete: A = 9 and B = 5.

Important Limitation: Memory Aliasing

The XOR swap algorithm only works if A and B occupy distinct memory locations. If A and B are references or pointers to the same memory address (such as swapping an array element with itself: swap(arr[i], arr[i])), the first operation A = A ^ B reduces the shared memory location to zero, permanently erasing the data.