Swapping two variables
Say we need to swap the values of two variables, a and b. This is a classic problem in programming and it can be accomplished in a few ways.
Using a temporary variable
This is the straightforward method; just use a temporary variable to avoid losing one of the variable values:
1 2 3 | temp = a a = b b = temp |
Accumulating one of the values
Use one of the variables to temporarily keep track of both variable values:
1 2 3 | a = a + b b = a - b a = a - b |
Using Exclusive-OR (XOR)
The exclusive-or binary operator takes two bits and returns 1 only if both values differ, 0 if equal:
| A | B | A XOR B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
The bitwise exclusive-or operator (^) will apply the exclusive-or operation on every pair of bits of the inputs.
01100110 ^ 01011110 -------- 00111000
Three interesting properties, given A, B = {0, 1}:
- A XOR 0 = A (i.e. A XOR 0 returns A whatever A)
- A XOR 1 = ~A (i.e. A XOR 1 returns A flipped)
- (A XOR B) XOR B = A
The third property requires further explanation. On the one hand, if B is 0 then, by 1), applying XOR B twice to A returns A itself. On the other, if B is 1 then we are flipping A twice by 2), which winds up returning A itself.
We base our last method of swapping two (integer) variables on those three properties:
1 2 3 4 5 6 | swap (A, B) { A = A ^ B; B = B ^ A; A = B ^ A; } |
More formally, the computation:
1 2 3 | A = A ^ B; B = B ^ A; A = B ^ A; |
is equivalent to:
1 | B = B ^ (A ^ B) = (A ^ B) ^ B = A |
At this point, B has the original value of A, therefore:
1 | A = A ^ (A ^ B) = (B ^ A) ^ A = B |
This last method is the most performant among them all.
Question
Now that we have sifted through these three methods of swapping two variables, question: which is the main advantage of the first over the others?
This work, unless otherwise expressly stated, is licensed under a Creative Commons Attribution 2.0 UK: England & Wales License.
Tags: programming
February 26th, 2010 at 4:39 PM
1. The first is faster. You should not worry about the memory allocation. If you arre writing machine code where allocations matter, you can use machine registers. If you have large objects to swap, you can usually swap their internals, which are usually accessed by pointers.
2. The first method works with all kinds of objects. The second and third work with integral types only. They fail especially badly on C pointers.
3. The second method fails spectacularly with disparate floating point numbers:
double a = 1.0e+20;
double b = 1.0;
a = a + b; /* a = 1.0e+20 */
b = a - b; /* b = 1.0e+20 */
a = a - b; /* a = 0.0 */
March 12th, 2010 at 10:37 AM
@Eric: Yes, the point two was what the answer I was looking for. Your example regarding floating point numbers is really clarifying. Always learning. Thanks!