Number of 1 Bits
FreeBit manipulationEasy71 of 75
The problem
Count the set bits in an unsigned 32-bit integer.
Example
13 = binary 1101 → 3
Need a hint?
Subtracting one changes the lowest set bit and the bits beneath it.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Repeatedly replace n with n & (n−1), increasing a counter each time, until n becomes zero. Each iteration removes exactly the lowest set bit. Use unsigned semantics or a fixed-width mask when the language treats bitwise values as signed.
Complexity
O(number of set bits) time, at most 32 iterations, and O(1) space.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.