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;
}

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

George Samaras said...


// can support: up to 64bit
// datatypes
// assumes: long long is 64bits
// returns: 0 -> if no zeros are
// present, eg. source == 2^64-1
// non zero, if,

unsigned char ffz_LSB_portable
(type_t source)
{

union
{
type_t t1;
unsigned long long t2;
}u;

unsigned char indx = 0;

u.t2 = ~u.t2;

while(u.t2>0)
{
indx++;
u.t2 >>= 1;
}

return indx;
}

//--------------------------------
// pseudo ASM AT&T[instr src dest]

mov local_var gen_reg_1

//not instr, sets ZF flag
not gen_reg_1

//forward jumps are expected to
//not be taken.check for 0xf..fff
//fallthrough(jz) is expected
jz label_1

// bsf undefined if source == 0
// in our case source == U_int_max
// remember the not op
// index stored at g_reg_2
bsf g_reg_1 g_reg_2

//non zero index
inc g_reg_2

//return without error
jmp label_2

//set error code, this is
//redundant if bsf-undefined is
//equal to zero, test it
label_1: mov $0 g_reg_2

//return
label_2: mov g_reg_2 ret_local_var

// we used zero to indicate an
// error, or absence of zero
// -----------------------------
// 1-based index to indicate the
// least significant zero
// -----------------------------
// code can be less general- speed
// xor more general - less speed, // with-without error detection