XOR swap

Swap two integers in place using three XORs, with no temporary variable.

Time O(1)Space O(1)Code C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

After a ^= b, a holds the XOR of both original values while b is untouched, so b ^= a then XORs b with that combined value, which cancels b's own bits and leaves the original a. Now a holds (original a) ^ (original b) and b holds (original a), so a ^= b cancels the original a bits and leaves the original b. Three XORs, no spare storage.

Code

public static void XorSwap(ref int a, ref int b) {
    a ^= b;
    b ^= a;
    a ^= b;
}

Tips

Trace it on paper once: label the two original values and confirm each step's algebra, since the bit rows alone can be hard to hold in your head.
This only works when a and b are different storage locations; a ^= a would zero the variable out.

In the .NET library

It is a neat trick but rarely used in real code: a normal temp-variable swap is clearer and, on most hardware, just as fast or faster.