Count Set Bits Brian Kernighan Algorithm in DSA Python - Time & Space Complexity

Time Complexity: Count Set Bits Brian Kernighan Algorithm

O(k)

Understanding Time Complexity

We want to understand how fast the Brian Kernighan algorithm counts the number of 1s in a binary number.

How does the time taken grow as the number gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def count_set_bits(n: int) -> int:
    count = 0
    while n:
        n &= (n - 1)  # Remove the rightmost set bit
        count += 1
    return count

This code counts how many bits are set to 1 in the binary form of the number n.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop runs once for each set bit in n.
• How many times: Equal to the number of 1s in the binary representation of n.

How Execution Grows With Input

The number of loop runs depends on how many 1s are in n, not the total number of bits.

Input Size (n)	Approx. Operations (loop runs)
10 (binary 1010)	2
100 (binary 1100100)	3
1000 (binary 1111101000)	6

Pattern observation: The loop count grows with the number of set bits, which can be much less than total bits.

Final Time Complexity

Time Complexity: O(k) where k is the number of set bits in n.

This means the time depends on how many 1s are in the number, not its size in bits.

Common Mistake

[X] Wrong: "The loop runs once for every bit in the number (total bits)."

[OK] Correct: The loop only runs for set bits, skipping zeros quickly, so it can be much faster.

Interview Connect

Knowing this algorithm shows you can optimize counting bits by focusing on set bits only, a useful skill in many coding problems.

Self-Check

"What if we changed the input to always have half of its bits set? How would the time complexity change?"