I used this particular "algorithm" twice in my codes, but I never explained it properly. There is no code here since the interesting part is the theory, however, you can
find an example in the selection sort code if you like.
The truth table of this operator is:
1 XOR 0 --> 1
0 XOR 1 --> 1
1 XOR 1 --> 0
0 XOR 0 --> 0
So if the bits are different, 1 is returned, otherwise the result is 0. The XOR has the following properties which are useful to understand the algorithm:
- Commutativity (as you may note): A XOR B is equal to B XOR A.
- Associativity: (A XOR B) XOR C is equal to A XOR (B XOR C) etc.
- Identity exists: for every A, A XOR 0 = A.
- Every element is the zero of itself: for each A, A XOR A = 0.
The algorithm works like this (A and B are integer variables to be swapped):
1) A = A XOR B
2) B = B XOR A
3) A = A XOR B
But what interests us is: why. Let's give a closer look on what it happens with these instructions.
After the instruction 1, A = A XOR B, B remains the same.
After the second, A = A XOR B, while B = B XOR (A XOR B) = A XOR (B XOR B) = A XOR 0 = A.
After the third, A = (A XOR B) XOR A = B for the same reason as before. B is still A.
A little note: this algorithm fails if the two variables point at the same memory location! They can have the same content and nothing happens, provided they're stored in different locations.
In fact, if you do A = A XOR A the location becomes zero, and continues to be zero after the other instructions (because it's XORed with itself, and 0 XOR 0 = 0).