Sunday, November 30, 2008

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

“Macha the dal in the microwave is done. The palak in the bowl on the table seems thawed enough, most of the ice has melted. Take a third bowl, put the dal in it, put the palak in the microwave bowl, and set it for 3 min.”

“Cha, if we could XOR swap the dal and palak we wouldn't need a third bowl da.”

As Charles ‘Peanuts’ Schulz said, "Happiness is a warm Nai." (and a hungry Nikhil and TS).

The title is the poor man’s swap program. It interchanges the values of ‘a’ and ‘b’ without using a third variable. The XOR swap does exactly the same thing, but the incisively analytical reader would of course prefer the XOR swap because it sounds cooler :-)



Pranesh Srinivasan said...


Oh, just a general point. The a+b, a-b .. thing can integer-overflow, but not the XOR thing. So, you might lose some palak :P.

shreevatsa said...

The XOR swap is also more useful in shortest-code contests, "a^=b^=a^=b;" being actually shorter than "std::swap(a,b);" :-)

The title I remember as the very first programming problem I ever solved, a long time ago... there's a nice little book called "How to Solve It by Computer" (seems not very popular outside India, surprisingly), whose very first chapter was devoted to "swap two variables" and pointing out why "a=b; b=a;" does not work, and your title is the method I could think of for one of the exercises and remember being excited for days about :P Sweet memories...

Implementing the solution in the title seems tricky for dal and palak (partly because the instruction set is different -- no MOV, only 'move'), but a swap without a third bowl is still possible if you have sieve-appropriate substances :)

Ramkumar R. Aiyengar said...

XOR swap is valid only for variables of the same type. One more reason why you couldn't have XOR swapped palak and dal, since one is a microwaveable bowl (variable here, palak being the data) and the other isn't. If both were microwaveable, you would have done what any compiler would have done to prevent the temporary variable, even without this technique, by altering its flow graph. You would have kept the palak bowl straight in the microwave :D

Mahesh Mahadevan said...

I wrote this in an email to a friend, but nothing beats blogging it!
a^=b^=a^=b; is just the supreme crack! (Shreevatsa, haven't seen you since 2003)

Sayan said...

Damn you vegetarians.

Kedar said...

well.. ur very clearly using the right variable type (microwavables) but the wrong data (palak?? wtf?)

i second sayan.. Damn u vegetarians..

Mohan K.V said...

@Pranesh: Ah, nice :-)

@Shreevatsa: Strong shortest code!

I'll try to find "How to solve it by computer" sometime. Reminds me of this very nice book "How to solve it" by Polya which I found in the college library. It disappeared in one of those periodic combing ops by the local library cleaning mafia, and I never thought of it afterward. Will definitely try finding it here.

Re. sieve-appropriate, we could also have a Moses-esque partition :-)

And glad to have been of nostalgic assistance :-)

@Dynamic thalai: Straight in the microwave - but that wouldn't be blog-worthy :P Plus it was steel anyway :)

@Nai: woof!

@Sayanda and W: Reminds me of this quote: "I didn't fight my way to the top of the food chain to become a vegetarian." -Anon :D

Czar said...

Ha ha ha!!!

Hilarious stuff.

Mohan K.V said...

@All, here's an interesting video 1 minute video Anand sent: