Bird
Raised Fist0

What is the worst-case time complexity of checking if a 32-bit integer n is a power of two using the expression n & (n - 1) == 0?

medium💡 Conceptual Thinking Q5 of Q15
Bit Manipulation - Power of Two
What is the worst-case time complexity of checking if a 32-bit integer n is a power of two using the expression n & (n - 1) == 0?
AO(1)
BO(log n)
CO(n)
DO(n log n)
Step-by-Step Solution
Solution:

  1. Step 1: Understand the operation

    The expression n & (n - 1) clears the lowest set bit of n.

  2. Step 2: Check if result is zero

    If n is a power of two, it has exactly one set bit, so n & (n - 1) equals zero.

  3. Step 3: Time complexity

    This operation involves a constant number of bitwise operations, independent of n's value.

  4. Final Answer:

    Option B -> Option B

  5. Quick Check:

    Bitwise ops are constant time [OK]
Quick Trick: Bitwise check runs in constant time [OK]
Common Mistakes:
MISTAKES
  • Assuming time depends on number size
  • Confusing bitwise ops with loops
Trap Explanation:
PITFALL
  • Thinking bitwise operations take time proportional to number size
Interviewer Note:
CONTEXT
  • Tests understanding of bitwise operation time complexity
Master "Power of Two" 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 2easy Gray Code - Gray Code - Quiz 15hard Maximum Product of Word Lengths - Maximum Product of Word Lengths - Quiz 6medium Maximum Product of Word Lengths - Maximum Product of Word Lengths - Quiz 8hard Number of 1 Bits (Hamming Weight) - Number of 1 Bits (Hamming Weight) - Quiz 6medium Power of Four - Power of Four - Quiz 7medium Reverse Bits - Reverse Bits - Quiz 8hard Single Number II (Three Copies) - Single Number II (Three Copies) - Quiz 3easy Single Number III (Two Singles) - Single Number III (Two Singles) - Quiz 6medium UTF-8 Validation - UTF-8 Validation - Quiz 1easy