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);
开发者_StackOverflow中文版 count++;
}
sum += count;
}
This does not work, however. What is wrong?
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.
精彩评论