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^{3} - 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.

## Top comments (0)