count the number of zero group bits in a number_问答_开发者

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

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.

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;
}

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.

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.

You can repeatedly use integer division and the modulo operator to extract the bits, and keep track of the groups within your loop. It sounds like a homework question, so I'm not sure how much of a service it does you to give you a full solution? Consider that you can use this algorithm to get the base-2 representation of a positive integer (in fact it works with any base >= 2):

int example = 40;
while (example > 0) {
    printf("%d\n", example % 2);
    example /= 2;
}

This will print out the bits in reverse order (that is, starting from the least significant). From here there's not much work to be done to count the groups you want to count. Should I go further or can you take it from here?

Try this code Didnt test it.. so do let me know if you find some bug

num is the input.

int main()
{
    int count = 0;

    int num = 0xF0000000, mask = 1; /*size of mask and num should be same. */

    int i;
    int flag= 1;


    i = sizeof(num) * 8;

    while(--i) {
         if(flag && !(num & mask)) {
            count++;
            flag = 0;
        }
        else if(num & mask)
            flag = 1;

    mask = mask<<1;
 }

 printf("\n%d\n",count);
 }

Thanks
cexpert
http://learnwithtechies.com