Saturday, July 10, 2010

Bitwise Set-Bit

Say you want to set a variable to '0' if an integer is 0, and '1' if an integer is non-zero.

You can do it this way:

int setBit(int x) {
return !!x;

If you want to instead emulate this behavior, you can do it some other ways.

If you know for sure the sign-bit is not set, then you can implement this behavior like this:

int setBit(int x) {
return (uint)(x + 0x7fffffff) >> 31;

This works because if any bits were set, then it ends up carrying a '1' over to bit #31 (the sign bit).

If you also want to include the sign bit into this, you can implement the setBit() function like this:

int setBit(int x) {
return (((uint)x >> 1) | (x&1)) + 0x7fffffff) >> 31;

Or you can use 64bit operations like this:

int setBit(int x) {
uint64 y = (uint64)(uint)x + 0xfffffffful;
return ((int*)&y)[1];

This trick isn't really useful when sticking to high level c++, but it can be useful when dealing with low level assembly.

With x86 if you don't wish to use the SETcc instruction, you can use a variation of the trick for full 32bit detection using the carry bit like so:

add eax, -1 // Add 0xffffffff to eax
rcl eax, 1 // Rotate with the carry bit so its in the lsb
and eax, 1 // AND with the carry bit

The above is nice because SETcc only sets the lower byte to 1/0, while this will set the full 32bit register to 1/0. Also because SETcc only modifies the lower byte, it can be a speed penalty with the CPU's pipeline as opposed to modifying the full 32bit register.

Also note that I use 'int' and 'uint' in this article to refer to 32 bit signed and unsigned ints.
And i use 'uint64' to refer to unsigned 64bit int.

No comments:

Post a Comment