Problem Description

Given an integer n, you need to determine if it is a power of two. Return true if n can be expressed as 2^x where x is some integer, otherwise return false.

For example:

• n = 1 returns true because 1 = 2^0
• n = 16 returns true because 16 = 2^4
• n = 3 returns false because there's no integer x such that 2^x = 3

The solution uses a clever bit manipulation trick. Powers of two have exactly one bit set to 1 in their binary representation (like 1000 for 8, 10000 for 16). When we compute n & (n-1), this operation removes the rightmost 1 bit from n. For powers of two, since there's only one 1 bit, this operation results in 0. The solution checks if n > 0 (to handle negative numbers and zero) and if n & (n-1) == 0 to determine if n is a power of two.

Intuition

Let's think about what makes a number a power of two in binary representation. Powers of two have a unique pattern:

• 1 = 2^0 = 0001
• 2 = 2^1 = 0010
• 4 = 2^2 = 0100
• 8 = 2^3 = 1000
• 16 = 2^4 = 10000

Notice that each power of two has exactly one bit set to 1, and all other bits are 0. This is the key insight.

Now, what happens when we subtract 1 from a power of two? Let's see:

• 8 = 1000, and 8 - 1 = 7 = 0111
• 16 = 10000, and 16 - 1 = 15 = 01111
• 4 = 0100, and 4 - 1 = 3 = 0011

When we subtract 1 from a power of two, all the bits after the single 1 bit get flipped to 1, and the original 1 bit becomes 0.

So when we perform the bitwise AND operation n & (n-1):

• For 8: 1000 & 0111 = 0000
• For 16: 10000 & 01111 = 00000
• For 4: 0100 & 0011 = 0000

The result is always 0 for powers of two! This happens because there's no overlapping 1 bits between n and n-1 when n is a power of two.

For non-powers of two, there will be multiple 1 bits, so n & (n-1) won't be zero. For example, 6 = 0110 and 5 = 0101, so 6 & 5 = 0100, which is not zero.

This elegant bit manipulation trick allows us to check if a number is a power of two in constant time with just one operation.

Solution Approach

The solution implements the bit manipulation technique where we use the expression n & (n - 1) to check if a number is a power of two.

The implementation consists of two key conditions:

1. Check if n > 0: This handles edge cases where n is negative or zero. Negative numbers and zero cannot be powers of two, so we need to filter them out first.

2. Check if (n & (n - 1)) == 0: This is the core bit manipulation check. As explained in the reference approach, the operation n & (n - 1) eliminates the rightmost 1 bit in the binary representation of n. Since powers of two have exactly one 1 bit in their binary form, this operation will result in 0 for all powers of two.

The algorithm works as follows:

• When n is a power of two (like 8 = 1000 in binary), subtracting 1 gives us 7 = 0111 in binary
• The bitwise AND between 1000 and 0111 results in 0000
• This pattern holds for all powers of two

For non-powers of two:

• Consider n = 6 = 0110 in binary
• n - 1 = 5 = 0101 in binary
• n & (n - 1) = 0110 & 0101 = 0100, which is not zero

The time complexity is O(1) since we're performing a constant number of operations regardless of the input size. The space complexity is also O(1) as we only use a fixed amount of extra space.

This bit manipulation approach is more efficient than alternative methods like repeatedly dividing by 2 or using logarithms, as it solves the problem with just a single bitwise operation.

Example Walkthrough

Let's walk through the solution with n = 8 to see how the bit manipulation works:

1. First, check if n > 0:

   • 8 > 0 ✓ (passes the first condition)

2. Convert to binary representation:

   • n = 8 in binary is 1000
   • n - 1 = 7 in binary is 0111

3. Perform the bitwise AND operation:

   n     = 1000
   n - 1 = 0111
   -----------
   n & (n-1) = 0000

   • Each bit position is ANDed:
     • Position 3: 1 & 0 = 0
     • Position 2: 0 & 1 = 0
     • Position 1: 0 & 1 = 0
     • Position 0: 0 & 1 = 0
   • Result: 0000 which equals 0

4. Check if (n & (n-1)) == 0:

   • 0 == 0 ✓ (passes the second condition)
   • Since both conditions are true, return true

Now let's contrast this with a non-power of two, n = 6:

1. Check if n > 0: 6 > 0 ✓

2. Binary representation:

   • n = 6 in binary is 0110
   • n - 1 = 5 in binary is 0101

3. Perform the bitwise AND:

   n     = 0110
   n - 1 = 0101
   -----------
   n & (n-1) = 0100

   • Result: 0100 which equals 4 (not zero!)

4. Check if (n & (n-1)) == 0:

   • 4 == 0 ✗ (fails the second condition)
   • Return false

The key insight: powers of two have only one 1 bit, so when we subtract 1, all bits flip from that position downward, creating no overlap when ANDed together.

Solution Implementation

Time and Space Complexity

The time complexity is O(1) because the algorithm performs a fixed number of operations regardless of the input size. It only executes:

1. One comparison operation (n > 0)
2. One subtraction operation (n - 1)
3. One bitwise AND operation (n & (n - 1))
4. One equality check (== 0)

All these operations are constant time operations that don't depend on the magnitude of n.

The space complexity is O(1) because the algorithm uses only a constant amount of extra space. No additional data structures are created, and the space usage doesn't grow with the input size. The function only uses the input parameter n and performs in-place bit manipulation without requiring any auxiliary space.

Common Pitfalls

1. Forgetting to Check for Non-Positive Numbers

One of the most common mistakes is omitting the n > 0 check and only relying on the bit manipulation (n & (n - 1)) == 0.

Why this is a problem:

• For n = 0: The expression 0 & (-1) equals 0, which would incorrectly return true
• For negative numbers: Some implementations might behave unexpectedly with negative integers in bitwise operations

Incorrect Implementation:

def isPowerOfTwo(self, n: int) -> bool:
    # Missing the n > 0 check!
    return (n & (n - 1)) == 0

Correct Implementation:

def isPowerOfTwo(self, n: int) -> bool:
    return n > 0 and (n & (n - 1)) == 0

2. Integer Overflow in Alternative Approaches

When using iterative multiplication or division approaches, developers might encounter overflow issues with very large numbers.

Problematic Alternative:

def isPowerOfTwo(self, n: int) -> bool:
    if n <= 0:
        return False
    power = 1
    while power < n:
        power *= 2  # Can overflow for large n
    return power == n

Better Approach: Stick with the bit manipulation solution which avoids overflow entirely.

3. Misunderstanding the Bit Operation

Some developers confuse the operation and use n & (n + 1) instead of n & (n - 1), or use other incorrect bitwise operations.

Common Mistakes:

# Wrong: Using n + 1 instead of n - 1
return n > 0 and (n & (n + 1)) == 0

# Wrong: Using OR instead of AND
return n > 0 and (n | (n - 1)) == 0

# Wrong: Checking if result equals 1 instead of 0
return n > 0 and (n & (n - 1)) == 1

4. Edge Case with n = 1

While the bit manipulation solution handles this correctly, developers implementing alternative solutions sometimes forget that 1 is a power of two (2^0 = 1).

Example of Incorrect Logic:

def isPowerOfTwo(self, n: int) -> bool:
    if n <= 1:  # Wrong! This excludes 1
        return False
    # ... rest of the logic

The bit manipulation approach elegantly handles all these cases without special treatment, making it both efficient and less error-prone.