http://skalkoto.blogspot.com/2008/01/bit-operations-find-first-zero-bit.html

If anybody cares here is an algorithm to find the first zero bit in a number:

Invert the number
Compute the two’s complement of the inverted number
AND the results of (1) and (2)
Find the position by computing the binary logarithm of (3)

e.x.
For the number 10110111

01001000
10111000
01001000 AND 10111000 = 00001000
log2(00001000) = 3

But in a x86 processor environment there is a more simple way to do this since Intel provides a specific assembly instruction for this purpose called bsfl. This instruction return the position (index) of the least significant bit set to 1 in a 32-bit word. By using inline assembly, someone can easily create a function that finds the first zero bit by inverting a number and feeding it to this instruction. For 8-bit numbers, the code for this in gcc would look like this:

/*
* find the position of the first 0 in a 8-bit array
*/
inline unsigned short find_first_zero(uint8_t bit_array)
{
unsigned pos = 0;

__asm__(“bsfl %1,%0\n\t”
“jne 1f\n\t”
“movl $32, %0\n”
“1:”
: “=r” (pos)
: “r” (~(bit_array)));

if (pos > 7)
return 8;

return (unsigned short) pos;
}

Advertisements