Count Set Bits Brian Kernighan Algorithm in DSA Python

Mental Model

Count how many 1s are in a number's binary form by removing the rightmost 1 one by one.

Analogy: Imagine you have a pile of coins (1s) and you keep taking away the last coin until none are left, counting each coin you remove.

Number: 13 (binary 1101)
Bits: 1 -> 1 -> 0 -> 1
Count how many 1s are here.

Dry Run Walkthrough

Input: number = 13 (binary 1101)

Goal: Count how many bits are set to 1 in the binary form of 13.

Step 1: Remove the rightmost set bit from 1101 (13).

1101 (13) & 1100 (12) = 1100 (12)

Why: This removes the last 1 bit, reducing the number of set bits by one.

Step 2: Remove the rightmost set bit from 1100 (12).

1100 (12) & 1011 (11) = 1000 (8)

Why: Again, remove the last 1 bit to count it.

Step 3: Remove the rightmost set bit from 1000 (8).

1000 (8) & 0111 (7) = 0000 (0)

Why: Last set bit removed, no more 1s left.

Result:

Final number is 0, total set bits counted = 3

Annotated Code

DSA Python

class Solution:
    def count_set_bits(self, n: int) -> int:
        count = 0
        while n > 0:
            n = n & (n - 1)  # remove rightmost set bit
            count += 1      # increment count for each removal
        return count

# Driver code
sol = Solution()
number = 13
print(sol.count_set_bits(number))

while n > 0:

continue until all set bits are removed

n = n & (n - 1) # remove rightmost set bit

remove the rightmost 1 bit from n

count += 1 # increment count for each removal

count how many set bits have been removed

Output

3

Complexity Analysis

Time: O(k) because it loops only as many times as there are set bits in the number

Space: O(1) because it uses only a few variables regardless of input size

vs Alternative: Better than checking every bit (O(log n)) because it skips zeros and only counts set bits

Edge Cases

number = 0 (no set bits)

returns 0 immediately as there are no set bits

DSA Python

while n > 0:

number = 1 (single set bit)

counts 1 set bit correctly

DSA Python

while n > 0:

number with all bits set (e.g., 7 for 3 bits)

counts all bits correctly

DSA Python

while n > 0:

When to Use This Pattern

When you need to count how many bits are 1 in a number efficiently, use Brian Kernighan's algorithm because it quickly removes one set bit at a time.

Common Mistakes

Mistake: Looping through all bits instead of only set bits, causing slower performance.
Fix: Use n = n & (n - 1) to jump directly to the next set bit.

Mistake: Not updating the number inside the loop, causing infinite loop.
Fix: Assign n = n & (n - 1) inside the loop to reduce n each iteration.

Summary

Counts the number of 1 bits in a number's binary form by removing the rightmost set bit repeatedly.

Use it when you want a fast way to count set bits without checking every bit.

The key insight is that n & (n - 1) removes the rightmost set bit, letting you count set bits efficiently.