Count Set Bits Brian Kernighan Algorithm in DSA C - 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 change as the number gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int countSetBits(int n) {
    int count = 0;
    while (n) {
        n = n & (n - 1);
        count++;
    }
    return count;
}
    

This code counts how many bits are set to 1 in the integer n using Brian Kernighan's method.

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 1 bits in n, not the total number of bits.

How Execution Grows With Input

Execution depends on how many 1s are in the number, not just its size.

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

Pattern observation: The loop runs as many times as there are 1s, so it grows with the number of set bits, not the total bits.

Final Time Complexity

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

This means the time grows with how many 1s are in the number, which can be much less than the total bits.

Common Mistake

[X] Wrong: "The loop always runs for all bits in the number (like 32 or 64 times)."

[OK] Correct: The loop only runs once per set bit, so if the number has few 1s, it runs fewer times.

Interview Connect

Understanding this algorithm shows you can optimize by focusing on important parts of data, a skill valued in problem solving.

Self-Check

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