Count Set Bits

Count the number of 1s in the binary representation of a non-negative integer.

bit-manipulation binary counting

Write a function `count_set_bits(n: int) -> int` that takes a non-negative integer `n` and returns the number of 1 bits in its binary representation. For example, the binary representation of 13 is `1101`, which contains three 1s. The input `n` will be between 0 and 10^9 inclusive. The solution must be efficient, ideally O(number of bits).

Constraints

0 <= n <= 10^9. The function should handle the maximum input within typical time limits.

Example

>>> count_set_bits(0)
0
>>> count_set_bits(5)
2
>>> count_set_bits(13)
3
>>> count_set_bits(255)
8

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think about using bitwise AND with 1 to check the least significant bit.

Shift the number right by 1 each iteration to process the next bit.

Alternatively, use the trick `n & (n-1)` to remove the lowest set bit.

You can also use Python's built-in `bin(n).count('1')` for a quick solution, but try to implement the logic manually for practice.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.