Bit Hacks: Find if a Number Is a Power of Two Without Math Function or Log Function

Problem: Given a positive integer, write a code to find if it is a power of two or not.

“A number is a power of two” means that it can be written as 2^x where x is an integer. For example:

• 8 is a power of two = 2³
• 12 is not a power of two since there exists no x such that 2^x = 8
• 32 is a power of two = 2⁵

Image by Matt Artz on Unsplash

The immediate solution: Take the log of the given number on base 2 and if you get an integer then the number is the power of two.

Another solution: Keep dividing the number by 2, in any iteration, if n%2 becomes !=0, and n is not 1 then the number is not a power of 2. If n becomes 1 then it is a power of 2. Example:

• 8 / 2 = 4 => 4 / 2 = 2 => 2 / 2 = 1
• 12 / 2 = 6 => 6 / 2 = 3 => 3 / 2 = 1.5
• 32 / 2 = 16 => 16 / 2 = 8 => 8 / 2 = 4 => 4 / 2 = 2 => 2 / 2 = 1

The above solutions work just fine, but what if we want to achieve a solution using bitwise operators only? There are many possible solutions as well. In this post, we’ll focus on two of them.

The & (AND) operator:

Compares each bit of the first operand to the corresponding bit of the second operand. If both bits are 1, the corresponding result is1. Otherwise, it’s 0. Example:

11001110
01101111 &
--------
01001110

Solution 1

return (num & -num) == num

Let’s try to explain why this works through an example. Consider the number 8, what it is in binary (assuming 32-bits)?

0000 0000 0000 0000 0000 0000 0000 1000

Now let’s calculate the representation of -8:

1111 1111 1111 1111 1111 1111 1111 1000

How did we calculate that? A good way to remember how to represent negative numbers (two’s complement) is to begin from the rightmost bit, as long as you have 0’s, proceed to the left bit, and stop when you see 1 for the first time. Leave that 1, but from now on flip every bit until you reach the leftmost bit (inclusive).

Finally, let’s calculate 8 & -8:

0000 0000 0000 0000 0000 0000 0000 1000   8
↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓   &
1111 1111 1111 1111 1111 1111 1111 1000  -8
---------------------------------------
0000 0000 0000 0000 0000 0000 0000 1000   8    ¯\_(ツ)_/¯

Now let’s take another example, let’s say 7, which is not a power of two.

0000 0000 0000 0000 0000 0000 0000 0111   7
↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓ ↓↓↓↓   &                       
1111 1111 1111 1111 1111 1111 1111 1001  -7
---------------------------------------
0000 0000 0000 0000 0000 0000 0000 0001  != 7  ¯\_(ة_ة)_/¯

Note: I’ll leave it for you to handle the edge case where num is 0 :)

Solution 2

input & (input - 1) == 0 && input > 0

Following the same explanations from the first solution, this one should be straightforward:

If n is a power of 2, then its binary will look like:

1000000...

n - 1 looks exactly the opposite:

0111111...

Applying & on the two numbers yields 0.

Summary

Getting familiar with bitwise operators can shorten and improve your code in terms of performance, and that’s because bitwise operations are usually faster. On the other hand, it might add some complexity to the code clarity. If you’re doing low-level programming, you will probably benefit a lot from bitwise operations.