Swap Two Int Variables Without Extra Space

Swapping two int variables is a basic and common operation that every programmer all knows. I learnt it long time ago in the first C-language class during my undergraduate study. We can implement this function with C language as below:

void swap(int* a, int* b) {
 int temp = *a;
 *a = *b;
 *b = temp;
}

I have nothing to say about this. However, what if you were not allowed to apply for extra space, even if using one temporary variable is forbidden. What are you gonna do?

It seems tricky but quite simple once you learn it. I will try to enlighten you step by step until you touch the key. Here we go!

First, let's read the code. This is one of the implementations to deal with the swapping without any other space consumption.

void swap_1(int* a, int* b) {
    *a = *a + *b;
    *b = *a - *b;
    *a = *a - *b;
}

It looks fantastic at first glance. The idea behind that is to store the information of the two variables in one of them and extract each in such a proper way later. If you think the code is not so straightforward, you can assign integer values to both a and b and check the final result. Under most circumstances, it goes well. But it is not a perfect implementation. It has a fatal bug.

When a and b are large numbers or in other cases, it may cause data overflow. In a 32-bit environment, "int" occupies 4 bytes and ranges from -2^31 to 2^31-1 (the top bit is the sign symbol and -1 exists to leave a position for zero). If both a and b are so large that the sum of them exceeds the threshold, line 2 overflows the bound of the data type. So the problem does exist. How to deal with it? To move on, we have to talk about it at a lower lever by performing bitwise XOR (exclusive OR).

The same goes on. Code first!

void swap_2(int* a, int* b) {
    *a = *a ^ *b;
    *b = *a ^ *b;
    *a = *a ^ *b;
}

This version seems to be more difficult to understand. Don't worry. I'll explain it with example. Let me enumerate all the cases to prove it works.

1. a = 0 & b = 0
0 ^ 0 = 0;
It is obvious that after all the XORs a and b are zeros too. The swapping works. :)

2. a = 0 & b = 1
0 ^ 1 = 1;
1 ^ 1 = 0;
1 ^ 0 = 1;
The above corresponds to the code line 2 to 4. It results the right swapping as well. :P

3. a = 1 & b = 0
1 ^ 0 = 1;
1 ^ 0 = 1;
1 ^ 1 = 0;
Right again. -)

4. a = 1 & b = 1
1 ^ 1 = 0;
0 ^ 1 = 1;
0 ^ 1 = 1;
It goes the right way finally. ^^

Till now, we have enumerated all the cases for one bit number. No matter what a and b are and how large they become, in the lower lever they are stored in binary format. We can do the bitwise XORs as the above to swap them. No overflow. No bug. It is perfect!

Sometimes you may be asked to write the code within two lines or in only one line. It is quite easy if you know the grammar of C language. We can gather these 3 lines like this:

void swap_3(int* a, int* b) {
    *b ^= *a ^= *b;
    *a ^= *b;
}

Or like this in one line:

void swap_4(int* a, int* b)
{
    *a ^= *b ^= *a ^= *b;
}

In summary, exclusive OR is an interesting operation, which I regard as a magic wand. Since it is the bitwise operation in the lower lever, it is much more efficient to process. I illustrate it not in a theoretical way but simple and easy to understand. I hope after reading this post you could think of this trick when the road runs out. The exclusive OR may help you out!

p.s. A cuter way to implement this provided by the FB guy:

void swap_5(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}