Thursday, January 03, 2008

Bit Operations: find first zero bit

If anybody cares here is an algorithm to find the first zero bit in a number:
  1. Invert the number
  2. Compute the two's complement of the inverted number
  3. AND the results of (1) and (2)
  4. Find the position by computing the binary logarithm of (3)
e.x.
For the number 10110111
  1. 01001000
  2. 10111000
  3. 01001000 AND 10111000 = 00001000
  4. 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;
}

5 comments:

LOLmachine said...

Hey, god work :-). But there are still some things in your algorithm that I don't like:
* You use log2, which needs a floating point to calculate, and integer to floating point is not very fast
* If the number is 0 the result is negative infinite

I improved your algorithm a little bit (C-code):

// From: http://tekpool.wordpress.com/category/bit-count/
int BitCount(unsigned int u)
{
unsigned int uCount;

uCount = u
- ((u >> 1) & 033333333333)
- ((u >> 2) & 011111111111);
return
((uCount + (uCount >> 3))
& 030707070707) % 63;
}

int First0Bit(int i)
{
i=~i;
return BitCount((i&(-i))-1);
}

I think this is very fast for int-sized datatypes(32 bit).

Greets

Anonymous said...

Superb, was a neat, fast algorithm. We need more of this, this use of C is a dying art.

Hugh

Belogradchik said...

here is mine:


public static function get_first_zero_bit($bits){
$bits = (int)$bits;
$mask = 1;
for($mask;($bits&$mask)!=0;$mask=($mask<<1));
return $mask;
}

sami25 said...

there's no need to use floating-point to compute binary logarithm

j.e.e.k said...

In realtime systems (where this task is needed to get the highest prior task slot) this is solved by means of a table. The advantage is the deterministic runtime (no looping depending on the input). The table maps the 256 8-bit values to correspondig position (of the first 0 or 1 or whatever you like).
This can be expanded for a larger bit scale with some hierarchical considerations: e.g. a 256 bit array is resolved to four 8-bit groups of 8 bytes which themselfs refering each to an 8-bit field (8 bit * 8 * 4 = 256). You need every time 3 table accesses to get the result. ;)
The bit field consists of 32 byte (1st level) + 4 byte (2nd level) + 1 byte (3rd level) for the hierachical structure (some kind of octal tree).