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!