231. Power of Two
Given an integer, write a function to determine if it is a power of two.
Example 1:
Input: 1
Output: true
Explanation: 20 = 1
Example 2:
Input: 16
Output: true
Explanation: 24 = 16
Example 3:
Input: 218
Output: false
Solution 1: Bit Counting
class Solution:
def isPowerOfTwo(self, n: int) -> bool:
count = 0
while n > 0:
count += 1
n = n & (n - 1)
return count == 1
This was my initial solution. It takes advantage of the fact that numbers that are powers of two only have one set bit in their binary representation.
For example:
2 => "10"
4 => "100"
8 => "1000"
16 => "10000"
etc...
So in order to solve, we count the number of bits that are set to “1” in our number. If count == 1, then we know that our number only has one set bit, and therefore is a power of two.
This solution works very quickly, but there are some trickier ones out there.
Solution 2: Logarithmic Properties
class Solution:
def isPowerOfTwo(self, n: int) -> bool:
if n <= 0:
return False
else:
return int(math.log2(n)) == math.log2(n)
This solution works by using Python’s built in log2() function. If a number is a power of two, then log base 2 will be an integer.
Examples:
log2(4) = 2
log2(8) = 3
log2(16) = 4
etc....
If a number isn’t a power of two, then the log2() function will return a decimal value. Therefore, we can just test to see whether or not the log2() result is the same as it is when we cast it to an int.
If both numbers are integers, there will be no change when we cast one to an int, and we then know that the original number is a power of two. However, if the number is a decimal, it will not be equal to itself once cast to an int.
Solution 3: Bit Counting, but Shorter
class Solution:
def isPowerOfTwo(self, n: int) -> bool:
return n > 0 and n & (n - 1) == 0
This solution is my favorite, and it takes advantage of another binary property: if a number only has one set bit, then n & (n - 1) == 0.
Let’s prove it with the number 8:
binary(8) = 1000
binary(8 - 1) = binary(7) = 0111
binary(8) & binary(7) = 1000 & 0111 = 0
Therefore, we can solve the problem by just checking that n > 0 and n & (n - 1) == 0.
Notes
These solutions are all pretty quick, and run in constant time. However, the simplest is the third, because it only has to perform three operations: greater than, subtraction, and bitwise AND.