Efficient way to get the index of the first 2 consecutive 1-bit

Question

I have this binary representation: 0b0110010

With gcc, there is the built-in function __builtin_ffs that will return one plus the index of the least significant 1-bit, which returns 2 for my example.

I'm searching for a efficient way to return the index of 2 consecutive 1-bit, which would be 5 for my example. The language is C and and I have 64 bits numbers * 1024 to check. Would be great if the solution can cover the case of N consecutive bits too.

The simple solution would be to iterate through the bits with right shift operation and use a mask but it's not efficient.

Answer 1

Since gcc already have the built in, one way to do it is to right shift the number by one bit, bitwise and with the original, then forward the work to __builtin_ffs, i.e.

__builtin_ffs((x >> 1) & x)

Note this uses compiler intrinsics and is by definition not portable.

On architectures like x86, there are built in assembly instructions for bit scan (bsf). A hand-written C implementation is unlikely to perform better than that.