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

2 comments:

  1. Am I correct in saying that the "bitwise" solution is the most useful when applied to SIMD? Since it's a condition-free computational process that can be applied equally across entire arrays of data -- and since SETcc stuff typically doesn't exist on SIMD instruction sets.

    So even when it seems less intuitive, a bitwise solution is good to know because can still be useful where SIMD-style data operations are involved.

    ReplyDelete
  2. Yup that's an excellent point. The bitwise solution will allow you to do this on multiple vectors of the SIMD reg at once without needing any conditional jumps or jump-tables.

    Since SSE2 has integer comparison operations, you can use another bitwise solution other than the one above:

    PXOR xmm1, xmm1 // Set xmm1 to 0
    PCMPNED xmm0, xmm1 // Set xmm0 to all 1's if not equal
    PSRLD xmm0, 31 // Logical right shift by 31

    If your SIMD instruction set didn't have integer comparison operations, then the bitwise solution in the blog post might be the way to go.

    ReplyDelete