Number of Zeros in the binary representation of an Integer

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

It is not really an answer to your main question, but you should rewrite your recursive function like this :

int num_of_zero(int num)
{
    int left_part_zeros;

    if (num == 0)
        return 0;

    left_part_zeros = num_of_zero(num >> 1);
    if ((num & 1) == 0)
        return left_part_zeros + 1;
    else
        return left_part_zeros;
}

Your implementation have a lot of problems, beside being completely unreadable.

Answer 3

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

Answer 4

Recursion is definitely overkill -- and besides, your code's quite buggy (it will not count any of the leading zeros of num!!!). A simple iteration, such as:

int num_of_zero(int num) {
  unsigned int unum = (unsigned int)num;
  int count;
  int i;

  for(i = 0; i < 32; ++i) {
    if(!(unum & 1)) ++count;
    unum >>= 1;
  }
  return count;
}

is correct and faster (can be coded more concisely, but I think this is the clearest expression).

If you have to do this computation many times, consider precomputing an array of (say) 256 "counts of zeros" (each value giving the count for its index, 0 to 255 included, as an 8-bit number). Then you can loop just 4 times (masking and shifting 8 bits at a time), and easily unroll the loop -- if your compiler's not smart enough to do it on your behalf;-).

Answer 5

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.

Answer 6

I'm guessing that this is a homework question. No problem! Here's the fastest possible solution (after a long startup cost):

Make an array of byte that is 2³² long. Precompute the value of the number of zeros in the binary representation for each possible int value to fill in that array. From then on, you'll have an array that will give you the number of zeros per value.

Yes, that solution is silly -- it's a lot of work for little gain -- but combine it with one other idea:

What happens if you just precompute the values that are 8 bits long? Would you be able to write code that, though not quite as fast, would still return the number of 0-bits in a int?

What happens if you just precompute the values that are 4 bits long? 2 bits long? 1 bit long?

I hope this gives you ideas for a better algorthm...

Answer 7

The easiest way I found was to base it on something that counts the ones then simply subtract that from 32 (assuming that you're sure the int size is 32 bits).

int numberOfOnes (int num) {
    int count = 0;
    unsigned int u = (unsigned int)num;
    while (u != 0) {
        if ((u&1) == 1)
            count++;
        u >>= 1;
    }
    return count;
}
int numberOfZeros (int num) {
    return 32 - numberOfOnes (num);
}

This actually gives you both variants (ones and zeros) - there are faster ways to do it but I wouldn't consider them unless and until you know there's a performance problem. I tend to code for readability first.