How can I count amount of sequentially set bits in a byte from left to right until the first 0?

I'm not good in English, I can't ask it better, but please below:

if byte in binary is 1 0 0 0 0 0 0 0 th开发者_StackOverflow中文版en result is 1

if byte in binary is 1 1 0 0 0 0 0 0 then result is 2

if byte in binary is 1 1 1 0 0 0 0 0 then result is 3

if byte in binary is 1 1 1 1 0 0 0 0 then result is 4

if byte in binary is 1 1 1 1 1 0 0 0 then result is 5

if byte in binary is 1 1 1 1 1 1 0 0 then result is 6

if byte in binary is 1 1 1 1 1 1 1 0 then result is 7

if byte in binary is 1 1 1 1 1 1 1 1 then result is 8

But if for example the byte in binary is 1 1 1 0 * * * * then result is 3.

I would determine how many bit is set contiguous from left to right with one operation.

The results are not necessary numbers from 1-8, just something to distinguish. I think it's possible in one or two operations, but I don't know how.

If you don't know a solution as short as 2 operations, please write that too, and I won't try it anymore.

---

Easiest non-branching solution I can think of:

y=~x
y|=y>>4
y|=y>>2
y|=y>>1

Invert x, and extend the lefttmost 1-bit (which corresponds to the leftmost 0-bit in the non-inverted value) to the right. Will give distinct values (not 1-8 though, but it's pretty easy to do a mapping).

110* ****

turns into

001* ****
001* **1*
001* 1*1*
0011 1111

EDIT:

As pointed out in a different answer, using a precomputed lookup table is probably the fastets. Given only 8 bits, it's probably even feasible in terms of memory consumption.

EDIT:

Heh, woops, my bad.. You can skip the invert, and do ands instead.

x&=x>>4
x&=x>>2
x&=x>>1

here

110* ****

gives

110* **0*
110* 0*0*
1100 0000

As you can see all values beginning with 110 will result in the same output (1100 0000).

EDIT:

Actually, the 'and' version is based on undefined behavior (shifting negative numbers), and will usually do the right thing if using signed 8-bit (i.e. char, rather than unsigned char in C), but as I said the behavaior is undefined and might not always work.

---

I'd second a lookup table... otherwise you can also do something like:

unsigned long inverse_bitscan_reverse(unsigned long value)
{
    unsigned long bsr = 0;
    _BitScanReverse(&bsr, ~value); // x86 bsr instruction
    return bsr;
}

EDIT: Not that you have to be careful of the special case where "value" has no zeroed bits. See the documentation for _BitScanReverse.