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!!
