M G Harish

Monday, September 24, 2007

One-liner ABS Function using Binary Operators

A few days ago, my friend TJ, who always keeps finding innovative programming challenges, asked a question: "Can you implement abs() function without using any relational operators in C?". But he also insisted to do it without using if, for, while etc., any control and loop structures for that matter.

I immediately came up with this:
abs_x = sqrt(x*x);

But he is not a guy to get contented with such an answer. He told that sqrt() internally uses relational operators in its implementation. Well, true. The sqrt() function that is included in math.h uses series expansion methods, which use if() statement in one or the other way. So I had no choice but to find some other way. After struggling a lot, I came up with this which uses only binary operators and arithmetic operators:
abs_x = (x^((((x&(1 << (sizeof(int)*8-1))) >> (sizeof(int)*8-1)&1)*-1)) + (((x&(1 << (sizeof(int)*8-1))) >> (sizeof(int)*8-1))&1);

The sizeof() opeator is necessary only to generalize the expression for any size (16 bit or 32 bit) of the integers. Otherwise a smaller version of the same would suffice.

For 32 bit integers:
abs_x = (x^((((x&(1<<31))>>31)&1)*-1))+(((x&(1<<31))>>31)&1);

or
abs_x = (x^((((x&0x10000000)>>31)&1)*-1))+(((x&0x10000000)>>31)&1);

For 16 bit integers:
abs_x = (x^((((x&(1<<15))>>15)&1)*-1))+(((x&(1<<15))>>15)&1);

or
abs_x = (x^((((x&0x1000)>>15)&1)*-1))+(((x&0x1000)>>15)&1);

Does it seem complicated? As we know, in C, numbers are represented in Two's Complement method. In 2's complement method of representation, the most significant bit represents the sign of the number. This bit will be 0 if the number is positive and 1 if it is negative.

The idea is to first check the most significant bit of the number. If it is 1 we need to negate the number. To negate a number, we should find the one's complement the number and add 1. That is what is done in the above expression!!

Do you think it's a great piece of one-liner code? It would have been, if it was impossible to simplify it further like swapping code posted before. Yes! It can further be reduced! Look at this code:
abs_x = x*(-2*(((x&(1<<(sizeof(int)*8-1)))>>(sizeof(int)*8-1))&1)+1);

For specific length, it looks like (for 32 bit integer):
abs_x = x*(-2*(((x&(1<<31))>>31)&1)+1);

All this code does is to multiply the original number with -1 if it is negative and with 1 if it is positive! Short and sweet one-liner, isn't it? But I can't say it's the shortest like I did in my earlier post. Feel free to express your opinions!

UPDATE
I guess thinking a lot certainly helps! I was able to find a still shorter one-liner!!
abs_x = x+2*x*(x>>(sizeof(int)*8-1));

Can I say this is the shortest? I still doubt!!

Like the post? You may want to...
Digg this

2 comments:

Anonymous said...

This is extremely good. Good informative topic.

Harisha - ಹರೀಶ said...

Thanks Sriram for your kind words :)

Keep visiting :)