quiz

Question: Write a function to swap anumber in place (that is, without temporary variables).

(Cracking the coding interview 16.1 Number Swapper)

Solution:

This is a classic interview problem, and it’s a reasonably straightforward one. We’ll walk through this using a0 to indicate the original value of a and b0 to indicate the original value of b. We will alson use diff to indicate the value of a0 - b0.

Let’s picture these on a number line for the case where a > b.

First, we briefly set a to diff, which is the right side of the above number line. Then, when we add b and diff (and store that value in b), we get a0. We now have b = a0 and a = diff. All that’s left to do is to set a equal to a0 - diff, which is just b - a.

The code below implements this.

1
2
3
4

a = a - b; // a = 9 - 4 = 5
b = a + b; // b = 4 + 5 = 9
a = b - a; // a = 9 - 5 = 4

We can implement a similar solution with bit manipulation. The benefit of this solution is that it works for more data types than just integers.

1
2
3
4

// Example for a = 101 (in binary) and b = 110
a = a^b; // a = 101^110 = 011
b = a^b; // b = 011^110 = 101
a = a^b; // a = 011^101 = 110

This code works by using XORs. The easiest way to see how this works is by focusing on a specific bit. If we can correctly swap two bits, then we know the entire operation works correctly.

1

1. x = x ^ y

This line essentially checks if x and y have different values. It will result in 1 if and only if x != y.

1

2. y = x ^ y

Or: y = {0 if originally same, 1 if different} ^ {original y}
Observe that XORing a bit with 1 always flips the bit, whereas XORing with 0 will never change it.
Therefore, if we do y = 1 ^ {original y} where x != y, then y will be flipped and therefore have x’s original value.
Otherwise, if x == y, then we do y = 0 ^ {original y} and the value of y does not change.
Either way, y will be equal to the original value of x.

1

3. x = x ^ y

Or: x = {0 if originaly same, 1 if different} ^ {original x}
At this point, y is equal to the original value of x. This line is essentialy equivalent to the line above it, but for different variables.
If we do x = 1 ^ {original x} when the values are different, x will be flipped.
If we do x = 0 ^ {original x} when the values are the same, x will not be changed.
This operation happens for each bit. Since it correctly swaps each bit, it will correctly swap the entire number.

Reference:
Cracking the Coding Interview, 6th Edition