Number of Zeros in the binary representation of an Integer

Possible Duplicate:
Best algorithm to count the number of set bits in a 32-bit integer?

Given a 32-bit integer N,Devise an algorithm to find the number of zeros in the binary bit representation of N.

The simplest algorithm I can think of is to check the binary representation for Zeros,in C something like this:

int num_of_zero(int num)
 {
   if(0 == num) return 1; /*For the input 0 it should output 1 */
   int Count = 0;
   while(num>0){
     if(0 == (num&1)) Count++;
    num >>= 1;
}
return Count;
}

I was wandering if there is some algorithm to compute at constant time.

For input 0 it should return 1 not 32 .

For 5 the output should be 1.As binary representation is 101 .

For 7 the output should be 0.

Precisely,I am looking for a better algorithm to compute number of (non-leading) zeros in the binary interpretation of an 32 bit integer.Hope the problem is clear now.

Edit: As pointed Alex Martelli,delroth I am modifying my code to made it more readable & using iteration this time.

---

The simple way to do this is to iterate over each bit of the binary representation of the number, test the value of each bit, and count up how many of them are zero. A loop would be much clearer than recursion for this.

There are many more optimized methods for doing this, though. You can find some of the better ones in answers to this question, "Best algorithm to count the number of set bits in a 32-bit integer" (obviously, the number of zero bits is the number of set bits subtracted from the total number of bits).

---

There's a great resource online called Bit Twiddling Hacks that contains all sorts of great little C tricks. You may be particularly interested in the Counting bits set section.

---

Quick and dumb way -- there are more exotic implementations in the duplicate question, but I have used something similar to this without much ill effect in the past.

We use a table of nibbles here to reduce the number of times the loop is run -- if you're doing a boatload of these computations, it might be more efficient to build a much bigger array, say, at the byte level, cutting the loop runs in half.

/* How many bits are set in every possible nibble. */
static size_t BIT_TABLE[] = {
    0, 1, 1, 2,     /* 0, 1, 2, 3 */
    1, 2, 2, 3,     /* 4, 5, 6, 7 */
    1, 2, 2, 3,     /* 8, 9, A, B */
    2, 3, 3, 4      /* C, D, E, F */
};

size_t num_of_bits(int num) {
    /* Little reworking could probably shrink the stack space in use here. */
    size_t ret = 0, i;
    register int work = num;

    /* Iterate every nibble, rotating the integer in place. */
    for(i = 0; i < (sizeof(num) * 2); i++) {
        /* Pointer math to get a member of the static array. */
        ret += *(BIT_TABLE + (work & 0xF));
        work >>= 4;
    }
    return ret;
}

链接地址: http://www.djcxy.com/p/72582.html

上一篇: 计数整数中的设定位数

下一篇: 整数的二进制表示中的零的数量