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;

}

## 5 comments:

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

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

Hugh

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;

}

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

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).

Post a Comment