Count Set Bits Brian Kernighan Algorithm in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Brian Kernighan's Algorithm for Counting Set Bits

What is the output of the following code that counts set bits using Brian Kernighan's algorithm?

DSA Python

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

print(count_set_bits(29))

A 4

B 5

C 3

D 6

💡 Hint

Count how many times the loop runs by removing the rightmost set bit each time.

The number 29 in binary is 11101, which has 4 set bits (1s). Brian Kernighan's algorithm removes one set bit per iteration, so the loop runs 4 times.

❓ Predict Output

intermediate

Result of Counting Set Bits for Zero

What is the output of the code when counting set bits of zero using Brian Kernighan's algorithm?

DSA Python

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

print(count_set_bits(0))

A None

B 1

C 0

D Error

💡 Hint

Zero has no set bits.

Zero in binary is 0, which has no set bits. The loop does not run, so count remains 0.

🧠 Conceptual

advanced

Why Brian Kernighan's Algorithm is Efficient

Why is Brian Kernighan's algorithm more efficient than checking each bit individually to count set bits?

A It converts the number to a string and counts '1's.

B It uses recursion to reduce time complexity.

C It uses a lookup table for all possible bit patterns.

D It loops only as many times as there are set bits, not total bits.

💡 Hint

Think about how many times the loop runs compared to total bits.

Brian Kernighan's algorithm removes one set bit per iteration, so it runs only as many times as there are set bits, making it faster than checking every bit.

🔧 Debug

advanced

Identify the Error in Modified Brian Kernighan's Code

What error will occur when running this modified code to count set bits?

DSA Python

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

print(count_set_bits(4))

A Infinite loop

B SyntaxError

C Returns 0

D Correct output 4

💡 Hint

Check how n changes each iteration with n & (n + 1).

The expression n & (n + 1) does not remove set bits correctly and can cause n to never become zero, leading to an infinite loop.

🚀 Application

expert

Number of Integers with Exactly k Set Bits in Range

How many integers between 0 and 15 (inclusive) have exactly 2 set bits? Use Brian Kernighan's algorithm to count set bits.

A 5

B 6

C 4

D 7

💡 Hint

List numbers 0 to 15 and count set bits for each.

Numbers with exactly 2 set bits between 0 and 15 are: 3(11), 5(101), 6(110), 9(1001), 10(1010), 12(1100). There are 6 such numbers.

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