count the number of zero group bits in a number

Question

How do you count the number of zero group bits in a number? group bits is any consecutive zero or one bits, for example, 2 is represented as ....0000000000000000010 has two zero bits groups the least significant bit and the group starts after one. Also, I am in a bad need for algorithms on bits manipulation if any one has a reference, please share

Answer 1

Here are some hints for you:

• if (x & 1) {...} checks if the least-significant bit of x is set;
• x >>= 1 shifts the value of x one bit to the right;
• mind the negative numbers when you do bit manipulation.

Answer 2

Here are a couple fun ways to do it. The #define-s at the beginning are only for being able to express the function inputs in binary notation. The two functions that do the work are variations on a theme: the first one uses a de Bruijn sequence and a lookup table to figure out how many trailing zeros there are in the parameter, and does the rest accordingly. The second uses a Mod37 table to do the same, which is very similar in concept but involves a modulo operation instead of a multiplication and a bit shift. One of them is faster. Too lazy to figure out which one.

This is a lot more code than the obvious solution. But this can be very effective if you have primarily zeros in the input, as it only requires one loop iteration (just one branch, actually) for every 1-bit, instead of one loop iteration for every bit.

#define HEX__(n) 0x##n##LU

#define B8__(x)  ((x&0x0000000FLU)?  1:0)   \
                +((x&0x000000F0LU)?  2:0)   \
                +((x&0x00000F00LU)?  4:0)   \
                +((x&0x0000F000LU)?  8:0)   \
                +((x&0x000F0000LU)? 16:0)   \
                +((x&0x00F00000LU)? 32:0)   \
                +((x&0x0F000000LU)? 64:0)   \
                +((x&0xF0000000LU)?128:0)

#define B8(d) ((unsigned char)B8__(HEX__(d)))

#define B16(dmsb,dlsb) (((unsigned short)B8(dmsb)<<8) + B8(dlsb))

#define B32(dmsb,db2,db3,dlsb) (((unsigned long)B8(dmsb)<<24) \
                              + ((unsigned long)B8(db2)<<16)  \
                              + ((unsigned long)B8(db3)<<8)   \
                              + B8(dlsb))

unsigned int count_zero_groups_debruijn(unsigned int v)
{
    // number of zero-bit groups (set to 1 if high-bit is zero)
    unsigned int g = (~(v & 0x80000000)) >> 31; 

    // lookup table for deBruijn 
    static const int _DeBruijnTable[32] = 
    {
        0,  1, 28,  2, 29, 14, 24,  3, 30, 22, 20, 15, 25, 17,  4,  8, 
        31, 27, 13, 23, 21, 19, 16,  7, 26, 12, 18,  6, 11,  5, 10,  9
    };

    do {
        // get number of trailing zeros in v
        int tz = _DeBruijnTable[((v & -v) * 0x077CB531U) >> 27];
        // increment zero group count if more than 1 trailing zero
        g += (tz > 0) * 1;
        // shift out trailing zeros and the preceding 1
        v = v >> (tz+1);
    } while (v);

    return g;
}

unsigned int count_zero_groups_mod37(unsigned int v)
{
    // number of zero-bit groups (set to 1 if high-bit is zero)
    unsigned int g = (~(v & 0x80000000)) >> 31; 

    // lookup table for mod37
    static const int _Mod37Table[] = 
    {
         0,  0,  1, 26,  2, 23, 27,  0,  3, 16, 24, 30, 28, 11,  0, 13,  4,
         7, 17,  0, 25, 22, 31, 15, 29, 10, 12,  6,  0, 21, 14,  9,  5, 20,
         8, 19, 18
    };

    do {
        // get number of trailing zeros in v
        int tz = _Mod37Table[(v & -v) % 37];
        // increment zero group count if more than 1 trailing zero
        g += (tz > 0) * 1;
        // shift out trailing zeros and the preceding 1
        v = v >> (tz+1);
    } while (v);

    return g;
}

int main(int argc, char* argv[])
{
    printf("zero groups: %d (should be 6)\n", count_zero_groups_debruijn(B32(10011001,10000000,00001001,00010011)));
    printf("zero groups: %d (should be 6)\n", count_zero_groups_debruijn(B32(10011001,10000000,00001001,00010000)));
    printf("zero groups: %d (should be 6)\n", count_zero_groups_debruijn(B32(00011001,10000000,00001001,00010001)));
    printf("zero groups: %d (should be 6)\n", count_zero_groups_debruijn(B32(00011001,10000000,00001001,00010000)));
    printf("zero groups: %d (should be 0)\n", count_zero_groups_debruijn(B32(11111111,11111111,11111111,11111111)));
    printf("zero groups: %d (should be 1)\n", count_zero_groups_debruijn(B32(00000000,00000000,00000000,00000000)));
    printf("zero groups: %d (should be 6)\n", count_zero_groups_mod37   (B32(10011001,10000000,00001001,00010011)));
    printf("zero groups: %d (should be 6)\n", count_zero_groups_mod37   (B32(10011001,10000000,00001001,00010000)));
    printf("zero groups: %d (should be 6)\n", count_zero_groups_mod37   (B32(00011001,10000000,00001001,00010001)));
    printf("zero groups: %d (should be 6)\n", count_zero_groups_mod37   (B32(00011001,10000000,00001001,00010000)));
    printf("zero groups: %d (should be 0)\n", count_zero_groups_mod37   (B32(11111111,11111111,11111111,11111111)));
    printf("zero groups: %d (should be 1)\n", count_zero_groups_mod37   (B32(00000000,00000000,00000000,00000000)));
    return 0;
}

Answer 3

The simpliest way is to count number of transitions from one to zero in loop using the shift of a bit mask along with bitwise `and' operation. It also necessary to check the first bit and increase obtained quantity by one if it is 0.

Answer 4

Andrew's solution is without doubt the simplest to design and implement, but I can't help but wonder if there is a quicker solution using bigger bit masks.

At a job interview I was asked to write some code to identify the most significant set bit. After spending a few minutes coming up with an ultra slim ultra fast binary search using shrinking bitmasks, which I kept suddenly realising could be optimised further, and further, resulting in large quantities of scribbles on lots of pieces of paper, the examiner looked at me blankly and asked if I knew how to use a for loop.

Maybe he should have just asked me to use a for loop to solve the problem.

Anyway it's not impossible that a similar such solution exists here.