Brian Kernighan count

Count the number of 1 bits in an integer using Brian Kernighan's algorithm.

bit-manipulation integers counting

Write a function `brian_kernighan_count(n: int) -> int` that returns the number of 1-bits (set bits) in the binary representation of a non-negative integer `n`. Use Brian Kernighan's algorithm: repeatedly clear the lowest set bit by performing `n &= n - 1` and count how many times you do this. Do not use built-in functions like `bin(n).count('1')` or `int.bit_count()`. The input `n` is a non-negative integer with 0 <= n <= 10^9. The function should return an integer.

Constraints

0 <= n <= 10^9 (fits in 32-bit signed integer). Expected time complexity O(k) where k is the number of set bits. The function must not use built-in bit-counting shortcuts.

Example

>>> brian_kernighan_count(0)
0
>>> brian_kernighan_count(7)
3
>>> brian_kernighan_count(255)
8
>>> brian_kernighan_count(1024)
1

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think about what `n & (n - 1)` does to the binary representation.

Each operation removes exactly one set bit, so loop until n becomes zero.

Initialize a counter to zero and increment each time you clear a bit.

Test Results

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