Checking if a number is a power of two is a fundamental bit manipulation task. While you could solve this by repeatedly dividing by 2, the bitwise approach is significantly more efficient, running in O(1) time.

Problem Statement

Given an integer n, return true if it is a power of two. Otherwise, return false. An integer n is a power of two if there exists an integer x such that n == 2^x.

Example 1

Input: n = 1

Output: True

Explanation: 2^0 = 1.

Example 2

Input: n = 16

Output: True

Explanation: 2^4 = 16.

Example 3

Input: n = 3

Output: False

Deep Dive: The Bitwise Logic

To understand why n & (n - 1) works, let's look at the binary representation of powers of two:

• 2: 0010
• 4: 0100
• 8: 1000

Notice that every power of two has exactly one bit set. When we subtract 1 from these numbers:

• 2-1 (1): 0001
• 4-1 (3): 0011
• 8-1 (7): 0111

By subtracting 1, the only set bit becomes 0, and all bits to its right become 1. When we perform a bitwise AND between the original number (n) and (n-1), all bits will result in 0.

Step-by-Step Algorithm

1. First, ensure n > 0. Negative numbers and zero cannot be powers of two.
2. Perform the bitwise calculation: result = n & (n - 1).
3. Check if the result == 0.

Python Implementation

def is_power_of_two(n):
    # A power of two must be positive and (n & n-1) must be 0
    return n > 0 and (n & (n - 1)) == 0

# Test cases
print(is_power_of_two(16)) # True
print(is_power_of_two(10)) # False
print(is_power_of_two(1))  # True

Complexity Analysis

• Time Complexity: O(1) - The bitwise AND operation takes constant time regardless of the size of the number.
• Space Complexity: O(1) - No extra space is required.

Complexity Analysis

• Time Complexity: O(1) for bitwise check.
• Space Complexity: O(1).