bit value check efficiency

Hello everyone,


I have a long array (char*) and I need to check which bit is the first bit whose value is 1.

I have two ways to implement,

1. Iterate each byte, then iterate each bit in each byte one by one;
2. Iterate each byte, and check whether the value of the byte itself is non-zero, if yes, then iterate each bit in the byte to find which bit is the first bit which is set to 1, or else skip this byte and continue to iterate next byte.

I think (2) is always faster, right? But I do not know why (2) is faster since it is just my personal estimation without any concrete basis analysis.


thanks in advance,
George

char * would be a pointer to a char or char array :).

I'd go with 2 (from bit 0 to CHAR_BIT), especially if you're looking for speed (the loop only runs for the size of the array + n (from non-zero byte to first 'on' bit)). Whereas 2 runs CHAR_BIT * size of the array times.

1, could look something like;

Code:

---

char longCharArray[] = "stuff and gruff";    /* whatever is supposed to be in here, crummy test data */
size_t i = 0, b = 0;

/* ... */

for(i = 0; i < sizeof(longCharArray); i++)
{
    /* non-zero byte */
    if(longCharArray[i] != 0)
    {
        /* find first 'on' bit */
        for(b = 0; b < CHAR_BIT; b++)
        {
            /* http://www.cprogramming.com/tutorial/bitwise_operators.html */
        }
    }
}

---

Need more information about the expected data.
Does every bit have a high chance of being set, or...
Is the data likely to contain long sequences of zeros before a one is found almost every time?

If each bit has a 50% chance of being set, then checking the whole byte first is useless. So no, number 2 is not always fastest.
If there are usually about 10 bytes of zeros at the start then checking each bit one at a time would be silly.

Note also that there are processor instructions that do things like "find first bit set" from either end of a 32-bit value.

If this is beyond what you can do [there is no intrinsic function and you don't want to use inline assembler] you could have a table of 256 values that return the highest bit within a byte, rather than checking each individual bit in a loop.
The table would look something like this:

Code:

---

char array[256] = { -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,  // 0..15
                                4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,  // 16..31
                                5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,  // 32..47
                                5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,  // 48..63
                                6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,  // 64
                                6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,  // .
                                6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,  // .
                                6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,  // 127
                                7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,  // 128
                                7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
                                7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
                                7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
                                7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
                                7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
                                7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
                                7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7 }; // 255

---

Now, you just have to count the number of bytes and add 8 for each byte, then follow the above table when you hit a non-zero.

--
Mats

Or you can go with a divide and conquer approach which gives the answer in 3 comparisons.

Just fill out this idea with the rest of the tests.

Code:

---

if ( c >= 0x10 ) { /* is it in bits 4 to 7 */
  if ( c >= 0x40 ) { /* is it in bits 6 or 7 */
  }
}

---

Branches are often less efficient than memory reads of an array. But it depends on how critical it is...

--
Mats