Topics / Bit Manipulation / Q7
How do you swap two numbers without a temporary variable?
Short answer: Use three XORs: a ^= b; b ^= a; a ^= b;. It is a well-known trick, but in real code a temporary variable is clearer and just as fast.
void xor_swap(int *a, int *b)
{
if (a != b) { /* same object would become 0 */
*a ^= *b;
*b ^= *a;
*a ^= *b;
}
}
Why it works: XOR is its own inverse (x ^ y ^ y == x).
| Step | a | b |
|---|---|---|
| start | A | B |
a ^= b |
A^B | B |
b ^= a |
A^B | B^(A^B) = A |
a ^= b |
(A^B)^A = B | A |
Arithmetic version: a = a + b; b = a - b; a = a - b; also works but can overflow on signed types, which is undefined behaviour.
Why not use it in production
- If
aandbalias the same memory, the first XOR sets it to 0 and the value is lost. Theif (a != b)guard fixes that. - The three operations depend on each other, so the CPU cannot overlap them. With a temporary, the compiler often turns the swap into register renaming and generates zero instructions.
- It is less readable.
Follow-up: "Swap two nibbles in a byte": (x >> 4) | (x << 4) on a uint8_t (then cast back to uint8_t).