Bit Manipulation - Counting Bits (0 to N)
Given the following code using Brian Kernighan's bit counting trick, what is the output of countBits(5)?
Given the following code using Brian Kernighan's bit counting trick, what is the output of countBits(5)?
easy🧾 Code Trace Q3 of Q15
Step-by-Step Solution
Solution:
Step 1: Trace countBits for i=0 to 5
0 -> 0 bits; 1 -> 1 bit; 2 (10) -> 1 bit; 3 (11) -> 2 bits; 4 (100) -> 1 bit; 5 (101) -> 2 bits.Step 2: Confirm output list matches counts
Output is [0,1,1,2,1,2].Final Answer:
Option A -> Option AQuick Check:
Matches expected counts for 0 to 5 [OK]
Quick Trick: Brian Kernighan's trick counts set bits by clearing lowest set bit [OK]
Common Mistakes:
MISTAKES- Off-by-one in loop
- Miscounting bits for 3 or 5
- Confusing count initialization
Trap Explanation:
PITFALL- Candidates often miscount bits for numbers with multiple set bits or forget to include 0.
Interviewer Note:
CONTEXT- Tests candidate's ability to trace bit manipulation code correctly
Master "Counting Bits (0 to N)" in Bit Manipulation
Want More Practice?
15+ quiz questions · All difficulty levels · Free
Free Signup - Practice All QuestionsMore Bit Manipulation Quizzes