231. Power of Two
Difficulty: Easy
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?
Solution:
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 2x 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:
-
20 = 1 →
1
in binary. -
21 = 2 →
10
in binary. -
22 = 4 →
100
in binary.
-
20 = 1 →
-
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 (binary011
). The AND operation 100 & 011 = 000 (0).
-
n = 4 (binary
Thus, the solution involves:
- Checking if the number is non-positive (returns
false
immediately). - 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) {
...
...
...
/**
* go to ./solution.php
*/
}
// 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:
-
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
. -
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 returnsfalse
.
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.
Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!
If you want more helpful content like this, feel free to follow me: