Find first "1" in binary number

algorithm, assembly, c, x86

Solution

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)

Problem

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?

Original source

Related problems