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:Or more generally, suppose that for some binary (associative, commutative) operator
#
there is an identityi
such thatand that for every value
x
there is a valuex'
such thatThen you can swap two values using that operator:
For addition,
x' = -x
, but forXOR
we havex XOR x = 0
so thatx' = x
, so that:reduces to