Exploring new ways

If you have ever been to programming, you will surely have been asked to write a program to swap two numbers (If you haven't bothered about this simple program, you need not have to continue reading this article). Even if you are not well versed with the concept of programming, you will be able to solve this problem in one or the other way. Well, that's good. But I am trying to do much more than that, something that involves the combination of knowledge, thinking and understanding. I will go on describing about it in C language, since that's the language I like and that's the language I speak!!

Let's get down to the business here. If you ask anyone to swap two numbers, he might do it in this way:

temp = a;
a = b;
b = temp;

That's right. But it needs one more variable, temp. So, let us think and find some other way that needs no extra variable. If you know simple arithmetic, you might come up with this way:

a = a + b;
b = a - b;
a = a - b;

Let us see how the above code works.. For example, if a = 5, b = 7 then a = a + b; makes a = 12. The next statement b = a - b; makes b = 5 and the final statement a = a - b; makes a = 7. As we see, the values of a and b are interchanged. Our goal is achieved. Wow, the extra variable is eliminated! But there is one more concern here. It uses addition operations instead of mere assignments as in the previous case. Yeah, but what's the problem with that? you might ask. Well, there is, and you will notice it if you know how the microprocessors calculate. Addition is not a logical operation. It is an arithmetic operation. It is a combination of Exclusive OR (XOR) operation and AND operation. (Although ALUs of modern processors take care of this and do the operation in same amount of time as that needed for individual XOR or AND operations, I am not going to stop here, I'm here to explore new ways!). So, is there any way of still improving this? Yes, there is...

Now, if we can somehow eliminate this combinational operation of XOR and AND, we can achieve some more efficiency. For that one needs the knowledge of bitwise operations and obviously needs to know binary arithmetic. Assuming that you know it, here is the way:

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

Going back to the same previous example of a = 5 (0101b), b = 7 (0111b) we get a = 2 (0010b) after the execution of the first statement. And after the second statement gets executed, we will have b = 5 (0101b) and after the execution of the third statement, we will finally have a = 7 (0111b) which is what we need.

Hmm, think it is the optimum, don't you? But I don't think so... If you know C, you will know that C provides shorthand operators. So, how about this:

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

Well, now no one can further compress it. Eh, you think that? Remember, C provides the provision to put multiple assignments in a single statement and the operations are carried out from right to left. So, I come up with this, which is nothing but the merging of the above three statements, which I think, is the optimized one.

a ^= b ^= a ^= b;

If you find any piece of code that beats it, let me and the rest of the world know...