Problem Description

Given an integer n, you need to determine if it is a power of four. Return true if n is a power of four, otherwise return false.

A number n is considered a power of four if there exists some integer x such that n == 4^x.

For example:

• 16 is a power of four because 16 = 4^2
• 1 is a power of four because 1 = 4^0
• 5 is not a power of four because there's no integer x where 4^x = 5

The solution uses bit manipulation to efficiently check this condition. The approach recognizes that powers of four have specific properties in their binary representation:

1. They must be positive numbers
2. They have exactly one 1 bit in their binary form (since 4^x = 2^(2x), making them powers of two)
3. That single 1 bit must appear at an even position (bit positions 0, 2, 4, 6, etc.)

The code checks these conditions using:

• n > 0 to ensure the number is positive
• (n & (n - 1)) == 0 to verify there's only one 1 bit (property of powers of two)
• (n & 0xAAAAAAAA) == 0 to ensure the 1 bit is at an even position (0xAAAAAAAA has 1s at all odd bit positions)

Intuition

The key insight starts with recognizing that any power of four can be expressed as 4^x = (2^2)^x = 2^(2x). This means every power of four is also a power of two, but not every power of two is a power of four.

Let's think about the binary representation of powers of four:

• 4^0 = 1 = 0001 (bit position 0)
• 4^1 = 4 = 0100 (bit position 2)
• 4^2 = 16 = 10000 (bit position 4)
• 4^3 = 64 = 1000000 (bit position 6)

We notice a pattern: powers of four have exactly one 1 bit, and this bit always appears at even positions (0, 2, 4, 6, ...).

This leads us to a three-step verification process:

First, we need to ensure the number is positive since negative numbers and zero cannot be powers of four.

Second, we need to verify it's a power of two. The trick (n & (n - 1)) == 0 works because subtracting 1 from a power of two flips all the bits after the single 1 bit. For example, 8 is 1000 and 7 is 0111. Their AND operation gives 0. This only happens for powers of two.

Third, we need to distinguish powers of four from other powers of two. Since powers of four have their single 1 bit at even positions, we can use a mask that has 1s at all odd positions. The hexadecimal 0xAAAAAAAA represents the binary pattern 10101010...10101010 (32 bits with 1s at odd positions). If our number is a power of four, its single 1 bit is at an even position, so ANDing with this mask will yield 0.

By combining these three checks, we can efficiently determine if a number is a power of four using only bitwise operations.

Solution Approach

The solution uses bit manipulation to efficiently determine if a number is a power of four. The implementation consists of three key checks combined with logical AND operations:

Step 1: Check if the number is positive

n > 0

This ensures we're dealing with a valid candidate since powers of four must be positive integers.

Step 2: Verify the number is a power of two

(n & (n - 1)) == 0

This clever bit manipulation trick works because:

• For any power of two, there's exactly one 1 bit in its binary representation
• When we subtract 1 from a power of two, all bits after the single 1 become 1, and the original 1 becomes 0
• Example: 16 is 10000, and 15 is 01111. Their bitwise AND is 00000
• This condition is only true for powers of two (and zero, which we've already excluded)

Step 3: Ensure the single 1 bit is at an even position

(n & 0xAAAAAAAA) == 0

The hexadecimal value 0xAAAAAAAA represents a 32-bit mask with the pattern 10101010101010101010101010101010:

• This mask has 1 bits at all odd positions (1, 3, 5, 7, ...)
• Powers of four have their single 1 bit at even positions (0, 2, 4, 6, ...)
• When we AND a power of four with this mask, the result is 0 because there's no overlap
• Example: 16 is 10000 (bit at position 4), AND with the mask gives 0

The final solution combines all three conditions:

return n > 0 and (n & (n - 1)) == 0 and (n & 0xAAAAAAAA) == 0

This approach has O(1) time complexity since we're performing a fixed number of bitwise operations, and O(1) space complexity as we only use a constant amount of extra space.

Example Walkthrough

Let's walk through the solution with two examples to see how the bit manipulation approach works.

Example 1: Is 16 a power of four?

First, let's convert 16 to binary: 16 = 0x00000010 = 00000000000000000000000000010000

Now let's check each condition:

1. Is n > 0?

   • Yes, 16 > 0 ✓

2. Is (n & (n - 1)) == 0?

   • n = 16 = 00000000000000000000000000010000
   • n - 1 = 15 = 00000000000000000000000000001111
   • n & (n - 1) = 00000000000000000000000000000000 = 0 ✓
   • This confirms 16 is a power of two

3. Is (n & 0xAAAAAAAA) == 0?

   • n = 16 = 00000000000000000000000000010000 (the 1 bit is at position 4, which is even)
   • 0xAAAAAAAA = 10101010101010101010101010101010 (1s at all odd positions)
   • n & 0xAAAAAAAA = 00000000000000000000000000000000 = 0 ✓
   • The single 1 bit in 16 doesn't overlap with any odd position bits

All conditions pass, so 16 is a power of four (16 = 4²).

Example 2: Is 8 a power of four?

Convert 8 to binary: 8 = 0x00000008 = 00000000000000000000000000001000

Check each condition:

1. Is n > 0?

   • Yes, 8 > 0 ✓

2. Is (n & (n - 1)) == 0?

   • n = 8 = 00000000000000000000000000001000
   • n - 1 = 7 = 00000000000000000000000000000111
   • n & (n - 1) = 00000000000000000000000000000000 = 0 ✓
   • This confirms 8 is a power of two

3. Is (n & 0xAAAAAAAA) == 0?

   • n = 8 = 00000000000000000000000000001000 (the 1 bit is at position 3, which is odd)
   • 0xAAAAAAAA = 10101010101010101010101010101010 (1s at all odd positions)
   • n & 0xAAAAAAAA = 00000000000000000000000000001000 = 8 ≠ 0 ✗
   • The single 1 bit in 8 overlaps with the odd position bit at position 3

The third condition fails, so 8 is not a power of four (it's 2³, not 4^x).

Solution Implementation

Time and Space Complexity

The time complexity is O(1) because the algorithm performs a fixed number of bitwise operations regardless of the input size. Specifically, it executes:

• One comparison operation (n > 0)
• Two bitwise AND operations (&)
• One subtraction operation (n - 1)
• Two equality checks (==)

All these operations take constant time for integer values.

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 depend on the input value n. The algorithm only uses the input parameter and performs in-place bitwise operations with constant values (0xAAAAAAAA is a hexadecimal constant).

Common Pitfalls

1. Incorrect Mask for Different Integer Sizes

The mask 0xAAAAAAAA assumes 32-bit integers. In systems with 64-bit integers or when dealing with very large numbers, this mask might not cover all necessary bit positions.

Problem Example:

# For a 64-bit system, 4^31 = 4611686018427387904
# Binary: 0100000000000000000000000000000000000000000000000000000000000000
# The bit is at position 62 (even), but 0xAAAAAAAA only covers first 32 bits
n = 4**31  # This is a valid power of four
# Using 0xAAAAAAAA might give incorrect results for large powers of four

Solution: Use a mask that covers all possible bit positions for your system:

def isPowerOfFour(self, n: int) -> bool:
    # Use 0xAAAAAAAAAAAAAAAA for 64-bit systems
    # Or use a more general approach
    return n > 0 and (n & (n - 1)) == 0 and (n & 0xAAAAAAAAAAAAAAAA) == 0

2. Forgetting Edge Cases

Not handling special cases like n = 0 or negative numbers before applying bit operations.

Problem Example:

# Without checking n > 0 first
def isPowerOfFour(self, n: int) -> bool:
    # This would incorrectly process n = 0 or n = -16
    return (n & (n - 1)) == 0 and (n & 0xAAAAAAAA) == 0
    # For n = 0: (0 & -1) == 0 is True, leading to wrong result

Solution: Always check for positive numbers first:

def isPowerOfFour(self, n: int) -> bool:
    if n <= 0:
        return False
    return (n & (n - 1)) == 0 and (n & 0xAAAAAAAA) == 0

3. Misunderstanding the Mask Pattern

Using the wrong mask value or misunderstanding which positions should be masked.

Problem Example:

# Incorrect mask - using 0x55555555 instead of 0xAAAAAAAA
def isPowerOfFour(self, n: int) -> bool:
    # 0x55555555 = 01010101010101010101010101010101 (bits at even positions)
    # This would check the opposite condition!
    return n > 0 and (n & (n - 1)) == 0 and (n & 0x55555555) == 0

Solution: Remember that 0xAAAAAAAA has 1s at ODD positions (1, 3, 5, ...), and we want the result to be 0:

def isPowerOfFour(self, n: int) -> bool:
    # 0xAAAAAAAA = 10101010101010101010101010101010
    # Powers of 4 have bits at EVEN positions (0, 2, 4, ...)
    return n > 0 and (n & (n - 1)) == 0 and (n & 0xAAAAAAAA) == 0

4. Alternative Approach Using Modulo

While the bit manipulation is elegant, a simpler (though potentially less efficient) approach exists:

def isPowerOfFour(self, n: int) -> bool:
    # Alternative: powers of 4 when divided by 3 always give remainder 1
    # This works because 4 ≡ 1 (mod 3), so 4^x ≡ 1^x ≡ 1 (mod 3)
    return n > 0 and (n & (n - 1)) == 0 and n % 3 == 1

This approach avoids the mask complexity but introduces a modulo operation.