Wednesday, September 21, 2011

-1 or 1 bitwise trick

Been a while since my last update, and been a long time since my last bitwise trick.

The Problem:
If you have a 32bit signed integer, return -1 if the number is negative, and return 1 if the number is positive (or 0).

The Typical Solution:

s32 sign(s32 x) {
return x < 0 ? -1 : 1;
}


The Bitwise Solution:

s32 sign(s32 x) {
return (x>>31)|1;
}


How does it work?
Well (x>>31) does a signed shift with the sign bit, which will return either -1 if the sign bit was set (because -1 in binary is all 1's), or 0 if the sign bit wasn't set.
But we want to return 1 when its positive; so what we do is OR the result with 1. (-1 | 1) == -1, and (0 | 1) == 1.
So we get the result we wanted without needing a branch, and only using 2 very fast bitwise operations :D