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.