Find the first “1” in binary number

Question

Possible duplicate:
Efficient bitwise operations for counting bits or searching for the right | left majority

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

eg. 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 seventh bit on 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

You are looking for x86 bit scan instructions

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

When using inline asm, make sure that both pos and input are the same storage class (2, 4, or 8 byte integers). This built-in function should not be a problem.

Most compilers have built-in functions that use this instruction, but MSVC is the only one I know that has a direct.

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

NOTE : if the input is 0 (no bit set), then the result will be undefined!

Here is the version that will put the predefined constant in pos if the input file 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 as you like. If you want a negative number, change size_t to ssize_t (type of signed size)

Answer 2

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

Answer 3

Yes, there is a faster way - without using macros.

Using your method, you can have up to 32 * 2 operations.

Here is the logarithmic algorithm.

First you divide the number in 2 shorts and check for the bottom 0 short. If 0, you go and check the high part, keeping the offset = 16. If not 0, go and check the low part, with the offset = 0. You will be left with the short and the offset

Then divide by 2 characters the rest and continue the same. You will be left with char and offset.

Then divide the char into 2 parts of 4 bits and check the same.

You will make a maximum log entry of 32 * 2.

Answer 4

The internal properties of MSVC _BitScanForward and _BitScanReverse .

You can find your arguments here , they are not too intuitive (the value you want is not a return value).

Answer 5

This is the fastest way to do this. If you are dealing with the potential of a few words, you can check the first word, and then the second and so on, and find the lowest non 0 word. You still have to move it though.