Bit count in array

Question

I know that to count the number of set bits in a number, the following code can do it:

int  t; // in which we want count how many bits are set
        // for instance, in 3 (011), there are 2 bits set
int count=0;
while (t > 0) {
    t &= (t - 1);
    count++;
}

Now an array example:

int x[] = {3, 5, 6, 8, 9, 7};

I have the following code:

int sum = 0;
int count;
for (int i = 0; i < x.length; i++) {
    count = 0;
    while (x[i] > 0){
        x[i] &= (x[i] - 1);
        count++;
    }
    sum += count;
}

This does not work, however. What is wrong?

Answer 1

Your code works fine for me except that length was undefined - maybe because you were using Java, not C as I first guessed. Anyway I got it working in C:

#include <stdio.h>

int main()
{
    int x[]={3,5,6,8,9,7};
    int sum=0;
    int count;
    for (int i=0;i<6;i++){
        count=0;
        while (x[i]>0){
            x[i]&=(x[i]-1);
            count++;
        }
        sum+=count;
    }

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

Output:

12

A simpler way is to bitshift in a loop and count the number of bits as they pass by.

count = 0;
while (t)
{
    count += t & 1;
    t >>= 1;
}

This page shows some more advanced algorithms including using a lookup table or a clever parallel algorithm. The method you are using is called "Brian Kernighan's way" on that page.

You could also see what your compiler provides, e.g.:

int __builtin_popcount (unsigned int x);

To avoid the possibility of introducing errors when using this code to get the total number of bits in the array you could keep it as a separate function and call it once per element in the array. This will simplify the code.