Power of 2, solving a google interview question. Playing with bits. 
Tags: computerscience, tutorial, javascript, career
Published: 2020-06-13 02:43:10

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. 

<h3>Brute Force</h3>

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

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

<h3>Percompute and Use Set<h3>

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: 

```javascript
  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. 

<strong>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.</strong>

So how do we relate <strong>power of 2<strong> and <strong>bits</strong>

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. 

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/ou64og0o0yz8ph0xpxyc.png)

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. 

```javascript 
   &: 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
```

<strong>Tip: if the question is regarding bit manipulation, first try solving with & and ^ operators</strong>

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. 

```javascript 
   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: 
```javascript 
   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:
```javascript 
   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 :

```javascript 
   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