💬 Discord
Sign In
NeetCode #862LC-231EasyBit Manipulation
← Back to All Problems

#862 · #231 · Power of Two(2 的幂)

📌 Problem Statement & Constraints

Given an integer n, return true if it is a power of two, otherwise false. Constraints: -2^31 <= n <= 2^31 - 1. The follow-up asks for a solution without loops or recursion.

💡 Core Algorithmic Approaches

  1. A power of two has exactly one set bit in its binary representation.
  2. Subtracting one turns that single set bit into a run of ones below it, so n & (n - 1) clears it to zero.
  3. For a power of two the expression is therefore 0, and for any other positive number it is non-zero.
  4. The check must also reject non-positive values, since zero and the negative powers (in two's complement) would otherwise slip through.

💻 Benchmark Python3 Implementation

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n > 0 and (n & (n - 1)) == 0   # a power of two has one set bit

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(1): a single bitwise operation.
💾 Space Complexity
O(1).

⚠️ Interview Pitfalls & Follow-ups

  • Omitting the n > 0 guard: n = 0 gives 0 & -1 == 0, which would be reported as a power of two.
  • Using n % 2 in a loop: correct but O(log n); the bit trick is O(1).
  • Confusing powers of two with even numbers: 6 is even but not a power of two.
  • Assuming n & (n - 1) == 0 alone suffices for negatives: in two's complement a negative value can satisfy it, so the sign check is required.