Find first "1" in binary number [duplicate]

Question

Possible Duplicate:
Efficient bitwise operations for counting bits or find the right|left most ones

Is there a fast way to find the first 1 in a (32 bit) binary number?

e.g. if I have the number 00000000 00000000 00000000 10000000

I want to calculate the value "7" (or "24", if read from the other side) since the first zero in the number is stored in the 7th bit from the right.

Is there a faster way to do this than

int pos=0;
int number = 127; //binary from above
while ((number>>pos) > 0) { pos++; }

?

Perhaps a specific x86 assembler instruction?

Answer 1

With gcc, you can use __builtin_ctz and __builtin_clz. ctz gives the number of trailing 0 bits, and clz gives the number of leading 0-bits.

Answer 2

You are looking for the bit scan instructions of x86

__inline__ size_t bsf(size_t input) {
    size_t pos;
    __asm__ ("bsf %1, %0" : "=r" (pos) : "rm" (input));
    return pos;
}

If using inline asm make sure that both pos and input are the same storage class (2, 4, or 8 byte integer types). This inline function should be no problem.

Most compilers have intrinsics that use this instruction, but MSVC is the only one i know that has the direct one.

For the highest order bit set use bsr instruction instead, same syntax.

NOTE: if input is 0 (no bits set) then the result is undefined!

Here is a version that will put a predefined constant into pos if the input is 0:

#define BIT_SCAN_IFZERO 0

__inline__ size_t bsf(size_t input) {
    size_t pos, ifzero = BIT_SCAN_IFZERO;
    __asm__ ( "bsf %1, %0\n\t"
              "cmovz %2, %0"
            : "=r" (pos)
            : "rm" (input)
            , "rm" (ifzero));
    return pos;
}

Define BIT_SCAN_IFZERO to whatever you like. If you want a negative number there then change size_t to ssize_t (signed size type)