1. Overview
In this tutorial, we’ll discuss the problem of checking whether a number is a power of two.
First, we’ll define the problem. Then we’ll give an example to explain it.
Finally, we’ll present three different approaches to solving this problem.
2. Defining the Problem
Given the positive integer 
, we need to check whether it’s a power of two or not.
Let’s take a look at the following examples:
-
Power of two 
. -
Power of two 
. -
Not a power of two. -
Not a power of two.
3. Loop Approach
3.1. Main Idea
When we check the power of two numbers, we can see that they’re written in binary representation, in a format like 
(one followed by zeros). So the main idea in this approach is to keep removing zeros from the end of the number until we reach a one.
Once we reach a one, we check whether the number becomes equal to 
after removing all the trailing zeros. If so, it means the given number is a power of two.
3.2. Algorithm
Let’s take a look at the implementation:
algorithm isPowerOfTwoUsingLoop(N):
// INPUT
// N = the number to check
// OUTPUT
// Returns true if N is a power of 2, false otherwise
while N > 0 and N mod 2 = 0:
N <- N / 2
if N = 1:
return true
else:
return false
Initially, as long as is even and greater than zero, it means there’s a zero at the end of the binary representation of . In this case, we divide by two to shift the binary representation to the right (remove the trailing zero). Once one of the previous conditions becomes false, we’ll break out of the loop.
In the end, if becomes equal to , it means the given number is a power of two, so we return 
. Otherwise, we return 
.
3.3. Complexity
The complexity of this algorithm is 
, where is the given number. The reason behind this complexity is that we’ll iterate over all the bits of the given number. The number of bits is equal to 
.
4. Binary Search Approach
4.1. Main Idea
The main idea in this approach is to use binary search to find whether a power of two that is equal to exists. Furthermore, the search will be on the exponential part of the number. So if the current power of two is less than , we’ll look for a bigger one.
On the other hand, if the current power of two is greater than , we’ll try to find a smaller power. Once we find a power 
that makes 
, we’ll return true.
However, if the binary search ends and we don’t find any power of two equal to , that means is not a power of two.
4.2. Algorithm
Let’s take a look at the implementation:
algorithm isPowerOfTwoUsingBinarySearch(N):
// INPUT
// N = the number to check
// OUTPUT
// Returns true if N is a power of 2, false otherwise
low <- 0
high <- log2(N)
while low <= high:
mid <- (low + high) / 2
if 2^mid = N:
return true
else if 2^mid < N:
low <- mid + 1
else:
high <- mid - 1
return false
Initially, we declare the boundaries of binary search. 
is the minimum power possible, and it’s equal to zero. Conversely, 
is the maximum power possible, and it’s equal to (number of bits in ).
Next, as long as the boundary is less than or equal to the boundary, we’ll take the 
as the exponential part of the number and check whether the generated power of two is equal to . If so, we’ll return true. Otherwise, we’ll check if the current number is less than . In this case, we’ll try to look for bigger power. If not, we’ll look for a smaller power.
Finally, if we don’t find any power of two equal to , we’ll return .
4.3. Complexity
The complexity of this algorithm is 
, where is the given number.
The complexity here is equal to the complexity of the binary search, which is 
, and 
here is because we have possible powers we want to check.
5. Bitmask Approach
5.1. Main Idea
The main idea here is that we’ll get the advantage of the binary representation of . Furthermore, the binary representation of any power of two numbers is in a format like 
. So if we delete one from a power of two, it becomes something like 
. Then if we take the bitwise-and operation between and 
, the result should be equal to zero if is a power of two. Otherwise, it’s not.
5.2. Algorithm
Let’s take a look at the implementation:
algorithm isPowerOfTwoUsingBitmask(N):
// INPUT
// N = the number to check
// OUTPUT
// Returns true if N is a power of 2, false otherwise
if N > 0 and (N bitwise-and (N - 1) = 0):
return true
else:
return false
We check if is greater than zero, since the smallest power of two is equal to one, and if the bitwise-and operation between and is equal to zero. If so, that means is a power of two. Otherwise, it’s not a power of two.
5.3. Complexity
The complexity of this algorithm is 
because we’re only doing one operation, which is the 
operation.
6. Conclusion
In this article, we presented the problem of checking whether a number is a power of two or not.
First, we provided an example to explain the problem. Then we gave three different approaches to solving this problem. Finally, we walked through their implementations, with each approach having a better time complexity than the previous one.