Bit Manipulation - Number of 1 Bits (Hamming Weight)
What is the time complexity of the brute force bit counting approach that checks each bit of a 32-bit integer one by one?
What is the time complexity of the brute force bit counting approach that checks each bit of a 32-bit integer one by one?
medium🪤 Complexity Trap Q13 of Q15
Step-by-Step Solution
Step 1: Identify input size
The input is an integer n, and the brute force method checks each bit by shifting until n becomes zero.Step 2: Analyze loop iterations
The number of iterations depends on the number of bits in n, which is proportional to log n.Final Answer:
Option A -> Option AQuick Check:
Loop runs approximately log n times, so complexity is O(log n) [OK]
Quick Trick: Number of bits in n is proportional to log n [OK]
Common Mistakes:
MISTAKES- Assuming fixed bit width means O(1)
- Confusing value magnitude with fixed bit size
Trap Explanation:
PITFALL- Fixed 32-bit size applies only if input size is fixed; if input is arbitrary integer, complexity depends on log n.
Interviewer Note:
CONTEXT- Tests understanding of complexity relative to input size and bit operations.
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