Question : Given an integer, write a function to determine if it is a power of two. (Range: 1 - 2^31-1)

Eg: Input : 16, Output : true since 2^4 = 16.

Input : 18, Output : false.

### Brute Force

So the obvious brute force approach will be to just divide 2 and check if it reaches 1.

```
var powerOftwo = function(n){
if(n<=0) return false;
while(n%2 == 0) n = n/2;
return n == 1;
}
```

### Percompute and Use Set

Since we're give that the range is in between 0 - 2^31-1, we could use this to precompute various possible output, save them into a set and cross check:

```
let set = new Set();
for(let i=0;i<31;i++){
set.add(Math.pow(2,i));
}
console.log(set);
var powerOfTwo = function(n){
if(set.has(n)) return true;
return false;
}
```

Now that we know what we want to accomplish, let's think about what google might expect from us.

**Tip : One common pattern I noticed is that whenever a company asks a question which looks easy on understand and easy to implement, that question has to be somehow related to bit manipulation.**

So how do we relate **power of 2 and bits**

As we know, for a computer everything boils down to a combination of 0's and 1's including numbers. So let's see how the numbers which represent 2^n for n=0 to 31 are represented in bit form.

So the common pattern here is that the numbers that are power of 2's have only 1 bit set to 1 and rest of it is 0.

So how do we use this to our advantage ? Let's look at what operations we have to work with.

```
&: and operator 1&1 = 1, 0 & anything = 0
|: or operator 0&0 = 0, 1 & anything = 1
^: xor operator x^x = 0, x^n = 1
~: negate ~1 = 0 | ~0 = 1
```

**Tip: if the question is regarding bit manipulation, first try solving with & and ^ operators**

Let's try solving this with & operator. But what should we & it with ?

Let's generate a number, if a number is odd, +1/-1 will generate an even number and vice versa.

Now that we have "&" operator and 2 numbers let put them together.

```
even number : 6 = 110
+1 : 7 = 111
-1 : 5 = 101
6&7 = 6 6&5 = 4
multiple of 2 : 16 = 10000
+1 : 17 = 10001
-1 : 15 = 01111
16&17 = 16 16&15 = 0
```

Here comes our solution, 16&15 becomes 0 since as proved earlier that a number if it's power of 2, has only 1 bit set, so n-1 will set all previous bit's from current position to 1.

eg:

```
8 : 1000 7: 0111 8&7 = 0
16: 10000 15: 01111 16&15 = 0
32: 100000 31: 011111 32&31 = 0
```

But at the same time if we use an odd number

eg:

```
17: 10001 16: 10000 17&16 = 16
```

From this we can say that n&(n-1) = 0, if n is power of 2.

Due to this our code boiled down to :

```
var powerOfTwo = function(n){
n = n&(n-1);
return n == 0;
}
```

Amazing isn't it ? How few bit manipulation cause such drastic results aand lead us to a more concise readable code.

If you want to practice something similar, solve this :

Question : Count the number of ones in the binary representation of the given number.

Comment your solution for this question :)

I hope you liked my explanation comment down below if I messed up somewhere.

github : https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/powerOfTwo.js

## Top comments (6)

Hi,

It should be

`const pow2 = n => n & ((n & (n-1)) == 0)`

to avoid return true for zero.Btw, thanks for sharing!

Thanks for pointing out and reading my article :), I made a mistake, the range is between 1 -> 2^31-1, my bad

6&5 = 4, not 5.

my bad, thanks for pointing out :)

Super quick solution would be just count the no of 1 in binary form. If its 1. Return true.

In C++ just do __builtin_popcount(n) == 1

Yep, it one of the solutions, you're in right direction now combine the solution of the original question with this.

hint : if n&n-1 = 0, it means that the rest of the bit is guaranteed set to 0, so no need to parse them.