Use XOR to swap two numbers in C#

[XOR]

Note that I don’t recommend this technique for swapping numbers. It’s mostly a clever trick that provides a lesson in the bitwise XOR operation. The code is much easier to understand if you just declare a temporary variable to make the swap.

This example uses the following code to swap two numbers without creating a temporary variable. If variables A and B originally hold values a and b, then the comments to the right of the code explain how the swap works.

// Swap the numbers.
A = A ^ B;      // A holds a ^ b.
B = B ^ A;      // B holds b ^ (a ^ b) = b ^ b ^ a = 0 ^ a = a.
A = A ^ B;      // A holds (a ^ b) ^ a = a ^ a ^ b = b.

The first statement makes A hold a ^ b.

The second statement makes B hold b ^ A. Because A now holds a ^ b, this is b ^ (a ^ b). The XOR operator is commutative (you can change the order of two operands) so this is the same as b ^ (b ^ a). XOR is also associative (you can change where the parentheses are) so this is the same as (b ^ b) ^ a. For any value b, b ^ b = 0 so this is the same as 0 ^ a. Finally for any value a, 0 ^ a = a. So when this statement is done executing, variable B holds the value a.

The third statement makes A hold A ^ B. Plugging in the current values held by the variables, this is (a ^ b) ^ a. Using the commutative and associative properties again, and the fact that a ^ a = 0 and 0 ^ b = b, this is the same as b.

When all three lines are finished, variable A holds value b and variable B holds value a.

You can use a similar trick with other operators that are commutative, associative, and invertible. For example, you can perform the swap with the * and / operators or with the + and - operators. For an exercise, give it a try. The XOR operator has the advantage that it won’t cause overflow.


Download Example   Follow me on Twitter   RSS feed   Donate




This entry was posted in algorithms, mathematics and tagged , , , , , , , , , , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *