Count Set Bits Brian Kernighan Algorithm in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does the Brian Kernighan algorithm count in a number?

It counts the number of set bits (1s) in the binary representation of the number.

intermediate

How does the Brian Kernighan algorithm reduce the number of operations compared to checking each bit?

It repeatedly clears the rightmost set bit, reducing the number of iterations to the number of set bits instead of total bits.

intermediate

Explain the operation n = n & (n - 1) in the Brian Kernighan algorithm.

This operation removes the rightmost set bit from n by turning it to 0, effectively reducing the count of set bits by one.

intermediate

What is the time complexity of the Brian Kernighan algorithm for counting set bits?

O(k), where k is the number of set bits in the number, making it efficient for sparse bit sets.

beginner

Provide a simple Python code snippet using Brian Kernighan algorithm to count set bits.

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

What does the expression n & (n - 1) do in the Brian Kernighan algorithm?

A Flips all bits of n

B Adds 1 to n

C Removes the rightmost set bit from n

D Checks if n is even

The expression n & (n - 1) clears the rightmost set bit in n.

What is the main advantage of Brian Kernighan algorithm over checking each bit individually?

A It counts unset bits instead

B It runs in constant time

C It uses no loops

D It only loops as many times as there are set bits

The algorithm loops only as many times as there are set bits, making it faster for numbers with few set bits.

If n = 12 (binary 1100), how many times will the loop run in Brian Kernighan algorithm?

A 2

B 4

C 3

D 1

12 in binary is 1100, which has 2 set bits, so the loop runs 2 times.

Which bitwise operator is essential in Brian Kernighan algorithm?

A OR (|)

B AND (&)

C NOT (~)

D XOR (^)

The AND operator (&) is used to clear the rightmost set bit.

What will be the output of count_set_bits(0) using Brian Kernighan algorithm?

A 0

B 1

C Undefined

D Error

0 has no set bits, so the count is 0.

Describe how Brian Kernighan algorithm counts set bits in a number.

Think about how the number changes each loop.

Explain why Brian Kernighan algorithm is more efficient than checking each bit one by one.

Focus on the number of loop iterations.