Algorithms to Check If a Number Is a Power of 2

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.