How to Swap Two Variables Without Using a Temp Variable

swap

With all the high-level languages in widespread use today, it is often easy to forget that at the end of the day, everything boils down to binary: ones and zeroes. This is shielded from us via multiple layers of abstraction. There is nothing wrong with using these abstractions; they have made great modern-day development possible. At the same time, they conceal some of the more intriguing quirks that are inherent in the binary system. This includes bitwise operations, and specifically an operation called a bitwise swap. This is a very efficient operation that can exchange the values of two variables of the same type without using an intermediary variable, and looks like this in C:

a ^= b;
b ^= a;
a ^= b;

That’s it. Three funny-lookings line of code. When complete, the variable a will contain the contents of variable b, and vice-versa. How is this magic accomplished? First, let’s see the “normal” way of swapping variables in C:

int a = 3;
int b = 5;
int temp = a;
a = b;
b = temp;

To understand the bitwise swap, it’s first important to understand the binary, or base-2 number system. But first, let’s better understand our usual base-10 number system. In this system, there are 10 possible values (0-9), and the value of each digit is multiplied by a power of 10 based on its right-to-left position, starting with the number 0.

For example, take the number 73:

3 is in the 0th place. So 3 x 100 = 3
7 is in the 1st place. So 7 x 101 = 70
Add 3 + 70 = 73

In a “base-2” number system, there are 2 possible values (0 and 1), and the value of each digit is multiplied by a power of 2 based on its right-to-left position, starting with the number 0.

For example, the number 73 is represented as 01001001 in binary:

1 is in the 0th place. So 1 x 20 = 1
0 is in the 1st place. So 0 x 21 = 0
0 is in the 2nd place. So 0 x 22 = 0
1 is in the 3rd place. So 1 x 23 = 8
0 is in the 4th place. So 0 x 24 = 0
0 is in the 5th place. So 0 x 25 = 0
1 is in the 6th place. So 1 x 26 = 64
0 is in the 7th place. So 0 x 27 = 0
Add 1 + 0 + 0 + 8 + 0 + 0 + 64 + 0 = 73

Notice that we group each 0 or 1 (binary unit, or bit for short) into groups of 8 called a byte. Why 8? Legend has it that it took 7 bits to contain all 128 alphanumeric symbols in the English language (ASCII), so hey, why not one more to make it an even number? To represent values larger than 8 bits, multiple bytes are grouped together.

Next we need to discuss the bitwise exclusive OR (XOR) operator in C. It is a very simple operator that compares each bit in its operands and outputs a 0 if they are the same or 1 if they are different. Here are all the different possibilities:

0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0

The ^= is simply the exclusive OR operator combined with the assignment operator, meaning that

a ^= b

is equivalent to:

a = a ^ b;

Now, let’s try a bitwise swap on our original values, one operation at a time:

int a = 3; // binary: 00000011
int b = 5; // binary: 00000101

First:
a ^= b;
a = a ^ b;
a = 00000011 ^ 00000101;
a = 00000110;

Next:
b ^= a
b = b ^ a;
b = 00000101 ^ 00000110
b = 00000011;

Finally:
a ^= b;
a = a ^ b;
a = 00000110 ^ 00000011;
a = 00000101;

Our ending values are:
a = 00000101, which is 5
b = 00000011, which is 3

We’ve magically swapped the values of a and b without using a temporary variable! We’ve saved on memory and CPU cycles by not allocating a new variable on the stack and copying the old value into and out of it! So should you get rid of all your temp variables and use bitwise swaps instead? Not exactly. Modern compilers are advanced enough to optimize boring old swaps to the point that they are just as efficient as the bitwise swap. Further, because the bitwise swap must be executed in strict sequence, modern CPU’s can’t take advantage of their new parallel instruction pipelines for faster processing. Finally, the bitwise swap is harder to understand in code than a simple temp variable swap. In other words, if there is a place where bitwise swaps belong, it’s probably among your geek friends and not in your iOS or .NET apps!

Advertisements

About Martin Rybak

I am a New York area software developer and MBA with 10+ years of server-side experience on the Microsoft stack. I've also been a native iOS developer since before the days of ARC. I architect and develop full-stack web applications, iOS apps, database systems, and backend services.

3 responses to “How to Swap Two Variables Without Using a Temp Variable

  1. Awesome stuff. I anticipate a good amount of pushback from the temporary variable manufacturers but I will personally never use them again.

  2. That’s the most smart method to swap 2 integers without a temp variable. Thanks for sharing.

  3. dominic

    1 problem is the two variables can’t be the same or they both will be equal to 0

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: