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.

Practice

1. What does the Brian Kernighan algorithm do when counting set bits in a number?

easy

A. It shifts the number to the right until it becomes zero without counting bits.

B. It counts the total number of digits in the number.

C. It converts the number to a string and counts the characters.

D. It repeatedly clears the least significant set bit until the number becomes zero.

Solution

1. Step 1: Understand the algorithm's main operation

   The Brian Kernighan algorithm clears the least significant set bit in each iteration by doing n = n & (n-1).

2. Step 2: Effect of clearing bits

   Each clearing reduces the number of set bits by one until the number becomes zero, counting how many bits were set.

3. Final Answer:

   It repeatedly clears the least significant set bit until the number becomes zero. -> Option D

4. Quick Check:

   Clearing bits counts set bits [OK]

Hint: Clear rightmost set bit repeatedly to count bits [OK]

Common Mistakes:

• Thinking it counts all digits, not just set bits
• Confusing bit shifting with bit clearing
• Counting characters in string form of number

2. Which of the following is the correct syntax to clear the least significant set bit in Python using Brian Kernighan's method?

easy

A. n = n & (n - 1)

B. n = n | (n - 1)

C. n = n ^ (n - 1)

D. n = n + (n - 1)

Solution

1. Step 1: Identify the bit clearing operation

   The correct operation to clear the least significant set bit is n = n & (n - 1).

2. Step 2: Understand why other options are incorrect

   Using OR, XOR, or addition does not clear the least significant set bit correctly.

3. Final Answer:

   n = n & (n - 1) -> Option A

4. Quick Check:

   Bit clear uses AND with n-1 [OK]

Hint: Use AND with n minus one to clear bits [OK]

Common Mistakes:

• Using OR instead of AND
• Using XOR which toggles bits
• Adding numbers instead of bitwise operations

3. What is the output of the following Python code using Brian Kernighan's algorithm?

def count_set_bits(n):
    count = 0
    while n:
        n = n & (n - 1)
        count += 1
    return count

print(count_set_bits(13))

medium

A. 3

B. 5

C. 4

D. 2

Solution

1. Step 1: Convert 13 to binary

   13 in binary is 1101, which has three set bits (1s).

2. Step 2: Count set bits using the algorithm

   Each iteration clears one set bit: 1101 -> 1100 -> 1000 -> 0000, total 3 times.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Binary 1101 has 3 set bits [OK]

Hint: Count 1s in binary of number [OK]

Common Mistakes:

• Counting total bits instead of set bits
• Miscounting binary digits
• Confusing decimal with binary

4. Find the error in the following code that tries to count set bits using Brian Kernighan's algorithm:

def count_set_bits(n):
    count = 0
    while n > 0:
        n = n & (n + 1)
        count += 1
    return count

print(count_set_bits(7))

medium

A. Loop condition should be n != 0

B. Missing initialization of count variable

C. Using n & (n + 1) instead of n & (n - 1)

D. Using addition instead of bitwise AND

Solution

1. Step 1: Identify the bit clearing operation

   The code uses n & (n + 1), which does not clear the least significant set bit correctly.

2. Step 2: Correct operation for clearing bits

   The correct operation is n = n & (n - 1) to clear the rightmost set bit.

3. Final Answer:

   Using n & (n + 1) instead of n & (n - 1) -> Option C

4. Quick Check:

   Use n & (n - 1) to clear bits [OK]

Hint: Use n & (n - 1), not n & (n + 1) [OK]

Common Mistakes:

• Using n & (n + 1) which is incorrect
• Confusing loop condition syntax
• Forgetting to initialize count

5. Given a list of integers, which code snippet correctly uses Brian Kernighan's algorithm to return a list of counts of set bits for each number?

nums = [3, 5, 7]

A) def count_bits_list(nums):
       return [bin(n).count('1') for n in nums]

B) def count_bits_list(nums):
       def count_set_bits(n):
           count = 0
           while n:
               n = n & (n - 1)
               count += 1
           return count
       return [count_set_bits(n) for n in nums]

C) def count_bits_list(nums):
       return [sum(int(d) for d in str(n)) for n in nums]

D) def count_bits_list(nums):
       return [len(str(n)) for n in nums]

hard

A. Option A uses built-in count of '1's in binary string.

B. Option B uses Brian Kernighan's algorithm correctly.

C. Option C sums digits of decimal string, not bits.

D. Option D counts decimal digits, not bits.

Solution

1. Step 1: Analyze the code snippets

   The first snippet uses Python's bin(n).count('1'), which counts set bits but not Brian Kernighan's algorithm. The second snippet implements the algorithm correctly using a while loop that clears the least significant set bit with n = n & (n - 1). The third sums the decimal digits, which is incorrect for bits. The fourth counts the length of the decimal string, also incorrect.

2. Step 2: Confirm correct implementation

   The second snippet defines count_set_bits using n = n & (n - 1) in a loop and applies it to each number via list comprehension, which is the proper use of Brian Kernighan's algorithm.

3. Final Answer:

   Option B uses Brian Kernighan's algorithm correctly. -> Option B

4. Quick Check:

   Correctly uses n & (n-1) loop [OK]

Hint: Use n & (n - 1) loop inside list comprehension [OK]

Common Mistakes:

• Using string digit sums instead of bits
• Counting decimal digits instead of set bits
• Confusing built-in binary count with algorithm