Bit Manipulation - Number of 1 Bits (Hamming Weight)
Consider two approaches to count set bits: (1) brute force checking each bit, and (2) Brian Kernighan's algorithm. When is the brute force approach preferable over Brian Kernighan's?
Consider two approaches to count set bits: (1) brute force checking each bit, and (2) Brian Kernighan's algorithm. When is the brute force approach preferable over Brian Kernighan's?
hard⚖️ Approach Comparison Q8 of Q15
Step-by-Step Solution
Solution:
Step 1: Compare the two approaches
Brute force always checks all bits; Brian Kernighan's depends on the number of set bits.Step 2: Consider fixed input size
For fixed 32-bit integers, brute force is simple and performance difference is minimal.Final Answer:
Option A -> Option AQuick Check:
Fixed input size negates performance advantage of Brian Kernighan's [OK]
Quick Trick: Fixed input size makes brute force acceptable [OK]
Common Mistakes:
MISTAKES- Assuming Brian Kernighan's always better
- Ignoring fixed input size context
Trap Explanation:
PITFALL- Candidates often overlook that fixed input size makes brute force practical and simpler.
Interviewer Note:
CONTEXT- Tests tradeoff reasoning between algorithmic approaches.
Master "Number of 1 Bits (Hamming Weight)" in Bit Manipulation
Want More Practice?
15+ quiz questions · All difficulty levels · Free
Free Signup - Practice All QuestionsMore Bit Manipulation Quizzes