Sunday, April 30, 2006

Swapping two integers in a one liner

I found some really cool one liner solutions to swap two integers without using a temporary variable. These were posted on "C/C++ Programming Puzzles" community on www.orkut.com. Some of them are listed here.

1. a+=b-=a=b-a;
2. a/=b=(a=a*b)/b;
3. a^=b^=a^=b; same as a=(b=(a=b^a)^b)^a; (Thanks to Robert Vukovic)
4. b=a+b-(a=b);

Each individually are cool solutions. But all of them have one big problem. These are not portable! C standard says that when a value of an operand is changed in the same expression at some other place, then the result of the expression is undefined. Try running the program on gcc with -Wall option. All the above one liners (which are really cool to begin with!) are plagued by that. So I feel the most portable way to achieve the goal is:

a = a xor b;
b = a xor b;
a = a xor b;
(by Harpreet)

Unfortunately it is not a one liner.

9 comments:

Robert Vukovic said...

Here is one liner:

j=(i=(j=i^j)^i)^j;

Anonymous said...

can u pls invite me to the orkut community?

Anonymous said...

Those are all undefined. Look up the phrase "sequence points".

Chris Bigart said...

Too bad using a temporary value will almost always be faster, as well as easier to read.

Sumant said...

I know! This is all for fun!

Anonymous said...

Please note that, apart from being cool, hard to read, and slower than a temporary value, most importantly, these constructs are *unsafe*, too.

Each of them has its own particular point of failure, but it's most obvious in the xor construct.

If a == b then this cool one-liner will put 0 in both a and b. Unless by mere coincidence a == b == 0 holds, this is not what you wanted.

Now, the problem is you cannot guarantee that a == b won't happen (except if they are both compile-time constants, which would make the whole thing absurd).
Errors like this are a real pain to track down. They burn many hours of precious developer time and are entirely unnecessary.

template//typename T\\ inline void swap(T& a, T& b) { T t = a; a = b; b = t; };
will let you swap two values in one line, too (the blog software won't let me write a proper template, but you get it)
Not only will it be faster, but it will also prevent people from throwing sharp things at you when they're asked to help you fix code that will occasionally crash and burn for no obvious reason.

Sumant said...

It is agreed that they are all hard to read, and all one liners completely overlook sequence point rules and therefore could possibly give compiler dependent answers. On gcc, all the XOR one-liners seem to be doing swapping correctly, even for a == b. But they are unsafe anyways. The one with a division, does not work for large integers and zero obviously.

The expanded (3 liner) version of XOR always yields a correct answer irrespective of the compiler used because it does not violate sequence point rules and hence it safe to use (even for a==b).

Anonymous said...

The portable one liner leverage comma operator:

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

Built-in comma operator IS a sequence point.

sudeepdino008 said...

a^=b^=a^b;

One liner in c++ for swapping 2 values.