231. Power of Two

[mah-shamim]

Topics: Math, Bit Manipulation, Recursion

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 == 2x.

Example 1:

• Input: n = 1
• Output: true
• Explanation: 20 = 1

Example 2:

• Input: n = 16
• Output: true
• Explanation: 24 = 16

Example 3:

• Input: n = 3
• Output: false

Constraints:

• -231 <= n <= 231 - 1

Follow up: Could you solve it without loops/recursion?

[mah-shamim]

We need to determine if a given integer n is a power of two. A number is considered a power of two if it can be expressed as 2^x where x is a non-negative integer. The solution should efficiently check this condition without using loops or recursion.

Approach

The approach leverages bit manipulation properties of numbers that are powers of two. Here's the key insight:

• Positive Check: Negative numbers and zero cannot be powers of two, so we immediately return false for these cases.
• Bit Manipulation: For positive numbers, a power of two in binary representation has exactly one '1' bit, with all other bits being '0'. For example:
  • 2⁰ = 1 → 1 in binary.
  • 2¹ = 2 → 10 in binary.
  • 2² = 4 → 100 in binary.
• Bitwise AND Trick: For any number n that is a power of two, the bitwise operation n & (n - 1) will yield zero. This is because subtracting 1 from n flips all the bits after the least significant '1' bit, making the bitwise AND result zero. For example:
  • n = 4 (binary 100), n - 1 = 3 (binary 011). The AND operation 100 & 011 = 000 (0).

Thus, the solution involves:

1. Checking if the number is non-positive (returns false immediately).
2. Applying the bitwise AND operation between n and n-1 to check if the result is zero.

Let's implement this solution in PHP: 231. Power of Two

<?php
/**
 * @param Integer $n
 * @return Boolean
 */
function isPowerOfTwo($n) {
    if ($n <= 0) {
        return false;
    }
    return ($n & ($n - 1)) === 0;
}

// Test cases
var_dump(isPowerOfTwo(1));   // true (2^0)
var_dump(isPowerOfTwo(16));  // true (2^4)
var_dump(isPowerOfTwo(3));   // false
var_dump(isPowerOfTwo(0));   // false
var_dump(isPowerOfTwo(-2));  // false
?>

Explanation:

1. Non-Positive Check: The function first checks if the input n is less than or equal to zero. Since powers of two must be positive, any non-positive input immediately returns false.
2. Bitwise AND Operation: For positive numbers, the function computes n & (n - 1). If this result is zero, it confirms that n has exactly one '1' bit in its binary representation, meaning n is a power of two. The function returns true in this case; otherwise, it returns false.

This approach efficiently checks the power of two condition in constant time O(1) using bitwise operations, avoiding the need for loops or recursion. The solution handles all edge cases, including zero and negative numbers, as well as the entire range of 32-bit integers.

[kovatz]

Thanks for solving the problem of "Power of Two"

[mah-shamim]

Thanks