XOR Swap

#programming/algorithm

XOR swap is to swap two numbers by using XOR^[1] without any extra space or variable.

#define swap_unsafe(a, b) (a^=b; b^=a; a^=b;) // Doesn't work when a and b are the same object - assigns zero to the object in that case

Check for distinct address since if they were equal, the algorighm would fold to a triple &a ^= &a resulting in zero.

#define swap(a, b) ((&(a) == &(b)) ? (a) : swap_unsafe(a, b)

Derivation: Use the XOR

A = A ^ B
B = A ^ B = (A ^ B) ^ B = A ^ (B ^ B) = A ^ 0 = A
A = A ^ B = (A ^ B) ^ A = (B ^ A) ^ A = B

Avoiding Use It in Practice

On modern CPU, the XOR technique can be slower then using a temporary variable to do swapping.^[1:1] Reason:

Moving value between registers regularly incurs zero latency, it's much more faster than XOR operation.
Modern CPU strive to execute instructions in parallel via instruction pipelines but in XOR swap, the inputs to each operation depends on the results of the previous operations, so they mush execute in sequential.