Detect if a number is power of 2 using bitwise operators

Reading time: 15 minutes | Coding time: 1 minutes

Algorithm

We need to check if a number is power of 2 or not.

An obvious and trivial solution which comes to mind is keep dividing the number by 2 until you cannot and check if the number is 1 or 0.

On thinking further, we see that we are taking O(log(n)) to solve such a simple problem.

Can this be improved?

Of course, and Bitwise operators come to our rescue. But before that we need to study simple property of binary number which are powers of 2.

Can you see where we are going?

The powers of 2 have only one set bit in their Binary representation.

Let me be more explicit. If we subtract 1 from a power of 2 what we get is 1s till the last unset bit and if we apply Bitwise AND operator we should get only zeros.

This whole algorithm has a complexity of O(1).

We can prove the correctness of algorithm.

Suppose if there is a 1 to the left of first set bit, i.e., it is not a power of 2. We can clearly see that n & (n - 1) will not return 0.

Hence, 16 is a power of 2.

Hence, 15 is not a power of 2.

Implementation

• C++

#include <iostream>
// Function to check if the number "x" is power of 4
bool is_power_of_2(int x)
{
	// Check if the number has only one set bit
	if ((x & (x - 1)) != 0)
		return false;
	return true;
}
int main(int argc, char *argv[])
{
	int n;
	std::cout << "Enter a number:" << std::endl;
	std::cin >> n;
	// Print the result
	std::cout << ((is_power_of_2(n)) ? "YES" : "NO") << std::endl;
	return 0;
}

Complexity

• Worst case time complexity: Θ(1)
• Average case time complexity: Θ(1)
• Best case time complexity: Θ(1)
• Space complexity: Θ(1)

Questions