Number of Zeros in the binary representation of an Integer [duplicate]

Question

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.

Answer 1

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).

Answer 2

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.