Which mathematical properties apply to XOR Swap algorithm (and similar bitwise operator algorithms)

algorithms

Assume you have two variables a and b, and you need to swap them, and for whatever reason, making a temporary variable for storage is not an option. This is the algorithm in pseudocode

a ← a XOR b
b ← a XOR b
a ← a XOR b

Based on examples I can see that this does work.

But, why does it work?

More specifically, how was this derived? Was it a mere coincidence that XOR such and such values does this? This question applies to all bitwise operators.

I understand perfectly what they do, and how they work, and various algorithms that take advantage of them. But, are there mathematical properties of these bitwise operators that these algorithms are derived from? What are those mathematical properties? And which of them apply to the specific example of an XOR swap?

Best Answer

This can be done with any invertable binary operation like XOR or addition. So you could just as well write:

 a ← a + b
 b ← a - b
 a ← a - b

Or more generally, suppose that for some binary (associative, commutative) operator # there is an identity i such that

x # i = i # x = x

and that for every value x there is a value x' such that

x # x' = i

Then you can swap two values using that operator:

a ← a # b
b ← a # b'
a ← a # b'

For addition, x' = -x, but for XOR we have x XOR x = 0 so that x' = x, so that:

a ← a XOR b
b ← a XOR b'
a ← a XOR b'

reduces to

a ← a XOR b
b ← a XOR b
a ← a XOR b