Bitwise Operations: Find If a Number Is a Power of Two

In this post, I'll show you how to find if a number is a power of two (2^x) without using loops or math functions.

"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 is no integer x that satisfies 2^x = 8

A solution using loops will look like:

while ((input != 2 && input % 2 == 0) || input == 1) {
  input /= 2;
}
return input == 2;

Compare to:

return (num & -num) == num;

We achieved the same thing, with O(1) time complexity. Let's go through an example to feel what's going on here.

Let our input be 8, and let's work on a binary system (assuming 32-bits). The binary representation of the number 8 is:

0000 0000 0000 0000 0000 0000 0000 1000

While -8 looks:

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 0s, 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).

Now let's & them:

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

As you can see, we got input as a result! So input & -input == input condition is met.

Now let's consider a non-power of two number, say 7. Again, let's write it and its negative representation in binary:

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

Give it a try for more examples and you'll get the general idea - If the number is a power of two, then there must be only one bit set in its binary representation. For example:

0000 0000 0000 1000 0000 0000 0000 0000 = 2^19

This is not the only solution, of course. Another solution using bitwise operations:

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

I'll leave it for you to verify this for the examples above, it should be straightforward.