Description
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.
Examples:
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: falseSolution in Python
Python
class Solution:
def isPowerOfTwo(self, n: int) -> bool:
# A power of two number should be greater than 0
if n <= 0:
return False
# A number is a power of two if it has only one '1' bit in its binary representation.
# For example:
# 2 (binary 10), 4 (binary 100), 8 (binary 1000), etc.
# The trick here is to use bitwise AND operation. For a power of two:
# n & (n - 1) == 0. This works because:
# For n = 16 (binary 10000), n - 1 = 15 (binary 01111),
# Performing n & (n - 1) results in 0 (binary 00000).
return (n & (n - 1)) == 0Explanation:
- Initial check:
- First, we check if
nis greater than 0. Powers of two are always positive, so any number less than or equal to zero is immediately returned asFalse.
- First, we check if
- Bitwise trick:
- The core of the solution relies on a property of binary representation of powers of two. A power of two in binary always has a single
1followed by zeros (e.g.,2is10,4is100,8is1000, etc.). - By subtracting 1 from such a number, we flip all the bits after the most significant
1. For example:16(binary10000) becomes15(binary01111).- If you perform a bitwise AND (
&) operation between these two, the result will always be0.
- This property only holds for powers of two, so any non-power of two will not satisfy this condition.
- The core of the solution relies on a property of binary representation of powers of two. A power of two in binary always has a single
Solution in Javascript
JavaScript
var isPowerOfTwo = function(n) {
// A power of two must be greater than 0
if (n <= 0) {
return false;
}
// The bitwise trick to determine if a number is a power of two.
// For a power of two:
// n & (n - 1) == 0
// This works because in the binary representation of a power of two,
// there's only one '1' bit and the rest are '0's. Subtracting 1 flips all
// the bits after the most significant '1'.
// For example, for n = 16 (binary 10000), n - 1 = 15 (binary 01111),
// n & (n - 1) results in 0 (binary 00000), which confirms that it's a power of two.
return (n & (n - 1)) === 0;
};Solution in Java
Java
class Solution {
public boolean isPowerOfTwo(int n) {
// A power of two must be greater than 0
if (n <= 0) {
return false;
}
return (n & (n - 1)) == 0;
}
}Solution in C#
C#
public class Solution {
public bool IsPowerOfTwo(int n) {
// A power of two must be greater than 0
if (n <= 0) {
return false;
}
return (n & (n - 1)) == 0;
}
}