Tuesday, October 4, 2011

Bitwise Set-Bit (#2)

In a past article, I've shown some ways to do this. This time I'll show you another way to do it that I just came up with.

The problem:
Return 1 if a 32bit integer is non-zero, else return 0. The return-type should be a 32bit integer.

The Typical Solution:

s32 setBit(s32 x) {
return x ? 1 : 0;
}


The Cooler Solution:

s32 setBit(s32 x) {
return !!x; // Forces it to a bool which is 1 or 0
}


The Bitwise Solution:

s32 setBit(s32 x) {
return (u32)(x | -x) >> 31;
}


The last one works because any non-zero integer will have its sign bit set either when negated or normally (if its already negative). The only number that won't have its sign bit set after ORing these results is 0. So we just logically-shift right by 31 to get a 1 or 0 value, which is what we wanted :D

Note 1: The bitwise trick in this case is not preferred, instead you should use the 'typical' or 'cool' solution, since the compiler will be able to optimize it better for the given architecture. On x86 there is a SETcc instruction which can be used which is likely faster than doing the bitwise trick since its less operations. This trick may still be useful to know though in-case you're doing asm or compiler work with some architecture that doesn't have a SETcc-like instruction (and you wish to avoid jumps). Although the method from my past article might be more helpful in this case.

Note 2: There is actually a number which has its sign bit set both normally and on negation, and that's the minimum-negative integer. With 32bit integers this number is -2147483648 (i.e. 0x80000000) (so with 32bit integers: 0x80000000 == -0x80000000).
Using this knowledge, we now learned another neat trick. You can detect the minimum negative integer by doing: bool isMinNeg = x == -x; // x can be an int type of any size