1246. Counting the Ones
For each of q numbers, print how many bits are set to 1 in its binary
representation, one answer per line.
The obvious loop shifts right 32 times and checks the last bit each time, which is correct and does fixed work whatever the number.
There is a better way worth knowing: n & (n - 1) clears the LOWEST set bit.
Subtracting one flips that bit to zero and turns everything below it to ones,
and the AND then wipes all of them. Repeating it until the number is zero takes
as many steps as there are bits set, which for a sparse number is far fewer than
32.
Constraints - `1 ≤ q ≤ 100000` - `0 ≤ n ≤ 1000000000000000000`
Input
The first line contains an integer q.
Each of the next q lines contains one non-negative integer.
Output
For each number print one integer on its own line: how many of its bits are 1.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.