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;

}

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

Wonderful post, till system thankful to all your team for sharing such best information about EPOS systems.

your information is very interesting.till system Thank you for sharing this post

Post a Comment