0

Given the following intermediate state of a bit counting function using Brian Kernighan's algorithm: after 2 iterations, n = 8 (binary 1000). How many set bits did the original input have at minimum?

hard🔄 Reverse Engineer Q9 of Q15

Bit Manipulation - Number of 1 Bits (Hamming Weight)

Given the following intermediate state of a bit counting function using Brian Kernighan's algorithm: after 2 iterations, n = 8 (binary 1000). How many set bits did the original input have at minimum?

AAt least 3 set bits

BExactly 2 set bits

CAt least 1 set bit

DAt least 4 set bits

Step-by-Step Solution

Solution:

Step 1: Understand Brian Kernighan's algorithm
Each iteration clears one set bit, so after 2 iterations, 2 bits have been cleared.
Step 2: Analyze remaining n=8
8 in binary is 1000, which has 1 set bit remaining.
Step 3: Calculate minimum original set bits
2 cleared bits + 1 remaining bit = at least 3 set bits originally.
Final Answer:
Option A -> Option A
Quick Check:
2 cleared bits + 1 remaining bit = 3 total [OK]

Quick Trick: Iterations count cleared bits, add remaining bits for total [OK]

Common Mistakes:

MISTAKES

Assuming iterations equal total bits
Ignoring remaining bits in n

Trap Explanation:

PITFALL

Candidates often forget to add remaining set bits after iterations.

Interviewer Note:

CONTEXT

Tests deep understanding of algorithm state and reverse reasoning.

Master "Number of 1 Bits (Hamming Weight)" in Bit Manipulation

3 interactive learning modes - each teaches the same concept differently

Try It Solution Trace

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions

More Bit Manipulation Quizzes