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;

}

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

// 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

In case anyone finds this from desperately searching the web for answers, you can also get the position of the first 0 bit in u by performing:

AND ~u, u+1

and then right-shifting the result until it's 0. The index you want will be numShifts-1.(this is the same as taking the binary log).

Post a Comment