XOR Algorithm Trick

XOR has a few useful properties:

1. x^0=x
2. x^x=0
3. x^y=y^x Commutative
4. Pairs within a sequence can be removed: x^y^x=y

Given this, you can swap a two variables without an intermediary variable:

x = x ^ y
y = x ^ y
x = x ^ y

This can also be used to find a missing or duplicated element within a set.

Assume a “main” set of 1-n. Assume a separate “missing” set containing all but 1 of the numbers. XOR all of the main set, XOR all of the missing set and then XOR these two values and you have the missing number.