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
Nice, although strictly speaking this isn't portable, because the result of right shifting a signed negative variable is implementation defined. *smartass mode off*
ReplyDeleteCheck out the book 'Hacker's Delight' by Henry Warren, sounds like you'd enjoy it.
Yup you're right, right-shift's behavior on signed integers is implementation defined in the c/c++ standards so the code isn't fully portable.
ReplyDeleteAt the same time though, almost every modern/popular architecture is likely to work with this (arm, mips, ppc, and x86 all have arithmetic right shift instructions).
The c++ standard leaves so many things undefined, that anything aside from trivial code may have different behavior on a different architecture. That's a huge reason I hate c++.
Thanks for the book suggestion, I hadn't heard about it :p
Btw ch, thanks again for the Hackers Delight book suggestion, I'm reading samples of it now and it looks awesome and full of bitwise tricks. It may have the potential to be my new favorite book.
ReplyDeleteOnly problem is it probably covers most of the possible bitwise tricks, so I won't feel clever anymore when I figure them out on my own lol.
You're welcome.
ReplyDeleteThe new volume of Knuth has a section on 'Bitwise Tricks' which might be of interest as well. I haven't read it though so I don't know if it's as good as HD.