Swapping two variables
Friday, February 26th, 2010Say 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?