void swap(ref int x, ref int y)
{ x = x ^ y; y = y ^ x; x = x ^ y; }
im learning about bitwise XOR. how is this swapping occurring? it's blowing my mind. this method is supposed to swap the contents of X and Y, but i dont understand AT ALL what is going on?
Wikipedia has an excellent explanation of the Swap-By-XOR algorithm.
The formal proof that this algorithm works is a bit involved, and requires the use of the mathematical properties of binary numbers.
But in simplified form, we can consider each bit of the binary value separate, since the XOR operation acts on each independently. As such, it's sufficient to show that this works with 1-bit values, since by induction we can demonstrate it works for any length binary value. It's quite simple to build an appropriate truth table for these operations, so I leave that out.
Swap by XOR is not the only "creative" swapping algorithm possible. A similar result can be achieved by using arithmetic operations:
void Swap( ref int x, ref int y )
{
x = x + y;
y = x - y;
x = x - y;
}
From a practical perspective, this is a technique that should be avoided in most cases. As you yourself recognize, the logic of this method is not immediately obvious and it can lead to maintainability and extensibility problems ... not the least of which is the fact that Swap( ref x, ref x ) will NOT do what the method's name implies (it will zero out the value, in fact).
Just look at it one bit at a time and one step at a time.
x|y -> x = x ^ y x|y -> y = y ^ x x|y -> x = x ^ x x|y
0|0 0|0 0|0 0|0
0|1 1|1 1|0 1|0
1|0 1|0 1|1 0|1
1|1 0|1 0|1 1|1
Here you can clearly see that the result in each case is a swapping of the bits. From here it is clear why it works in the general case. More formal explanations are possible.
Anytime you find yourself saying "I don't understand at all what is going on" is a strong indication that you should find a clearer way to write semantically-equivalent code.
XOR swaping is interesting - but on the other hand - is it really more efficient than swap by temp member? Compiler usually optimizes the code in such cases.
Beware. This method has a very very nasty property. It was used in one of the Underhanded C Contest entries. It will work happily... until one day someone tries something like swapping two array elements a[i] and a[j] without assuring that i!=j.
When both references refer to the same variable, this method zeroes it.
First of all look at how XOR works:
a | b | a^b
- - - - - -
0 | 0 | 0
1 | 0 | 1
0 | 1 | 1
1 | 1 | 0
So the result of an xor operation is 1 or true if the inputs are different, and 0 if the inputs are equal. Another way to look at it is to think of it as addition without carry, i'll denote it as (+) :
x = x ^ y <=> x = x (+) y;
y = y ^ x <=> y = y (+) x;
x = x ^ y <=> x = x (+) y;
First step : set all the bits that are 0 in x but 1 in y to 1. Now some bits are wrong in x because if a bit is 1 in x and also y it'll be set to 0. The other bits are correct.
Second step : Now set the same bit positions we set to 1 in x to 0 in y (we are done with y now). This works because x already has all bits that are different set to 1, so XORing y with x now basically means: toggle the bits in y that are set to 1 in x. We are done with y now :)
Third step : now we still need to set those bits in x to 1 that already were set to 1 originally and were reset to 0 after the first step back to 1. How ? We just XOR x with y one last time because what does xor do ? it sets a bit to 1 if the 2 inputs differ, which is exactly what we need.
If you are still confused about it you should just draw it on paper and play it through to see how it works and/or refer to the tables Jason did above.
swap() can be implemented with a single CPU instruction on most modern architectures (including i686 and x86_64). Hence, you are better off writing it in a way the compiler can recognize and convert accordingly rather than trying to micro optimize in a way that will actually make your code slower and less readable.