For each number, print how many of its bits are 1 (its population count).
Input
The first line has q (1 ≤ q ≤ 100). Each of the next q lines has a number from 0 to 4,294,967,295.
Output
One line per number: how many 1 bits it has.
Examples
Example 1 · Input
3 13 0 255
Expected output
3 0 8
Example 2 · Input
1 1024
Expected output
1
Hints
Hint 1
n & 1 is the lowest bit; n >> 1 drops it.
Hint 2
Or: n = n & (n - 1) clears the lowest 1 bit; count how many times until n is 0.
Hint 3
Use unsigned int so the shifts work for big numbers.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int main(void) {
int q;
scanf("%d", &q);
for (int i = 0; i < q; i++) {
unsigned int n;
scanf("%u", &n);
int ones = 0;
while (n != 0) {
n = n & (n - 1);
ones++;
}
printf("%d\n", ones);
}
return 0;
}