Bird
Raised Fist0

What is the time complexity of Brian Kernighan's algorithm for counting set bits in a 32-bit integer?

medium🪤 Complexity Trap Q5 of Q15
Bit Manipulation - Number of 1 Bits (Hamming Weight)
What is the time complexity of Brian Kernighan's algorithm for counting set bits in a 32-bit integer?
AO(n log n) due to bitwise operations
BO(32) because it checks all bits one by one
CO(1) constant time since input size is fixed
DO(k) where k is the number of set bits in the integer
Step-by-Step Solution
Solution:

  1. Step 1: Understand algorithm steps

    Each iteration clears one set bit, so loop runs k times where k is number of set bits.

  2. Step 2: Analyze complexity

    Time complexity depends on k, not total bits, so O(k).

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Loop runs once per set bit, not all bits [OK]
Quick Trick: Time depends on set bits count, not total bits [OK]
Common Mistakes:
MISTAKES
  • Assuming always O(32) ignoring set bits
  • Confusing bitwise ops with log factors
Trap Explanation:
PITFALL
  • Many think it always scans all bits, missing that it skips zero bits quickly.
Interviewer Note:
CONTEXT
  • Tests understanding of bit manipulation time complexity nuances.
Master "Number of 1 Bits (Hamming Weight)" in Bit Manipulation

3 interactive learning modes - each teaches the same concept differently

Try ItSolutionTrace

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More Bit Manipulation Quizzes
Bitwise AND of Numbers Range - Bitwise AND of Numbers Range - Quiz 15hard Find Two Missing Numbers - Find Two Missing Numbers - Quiz 4medium Find Two Missing Numbers - Find Two Missing Numbers - Quiz 7medium Generate All Permutations Using Bitmask DP - Generate All Permutations Using Bitmask DP - Quiz 9hard Gray Code - Gray Code - Quiz 13medium Maximum XOR of Two Numbers - Maximum XOR of Two Numbers - Quiz 5medium Power of Four - Power of Four - Quiz 5medium Power of Two - Power of Two - Quiz 7medium Reverse Bits - Reverse Bits - Quiz 15hard UTF-8 Validation - UTF-8 Validation - Quiz 13medium