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;
}
6 σχόλια:
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