# Optimized solution to calculate first powers of 2

Jun 21, 2015

The question is:

Calculate sum of first powers of 2 without using any built-in language API to calculate the power. Implement optimized solution.

Well, there are two factors. First, not using built-in functions like `Math.pow`

and second implementing the optimized solution. So, of course a recursive function or for-loop is not the answer.

## Answer

Use bitwise operations. How? Ok, let me show you a trick.

```
parseInt(10, '2') == Math.pow(2, 1); //2^1 = 2
parseInt(100, '2') == Math.pow(2, 2); //2^2 = 4
parseInt(1000, '2') == Math.pow(2, 3); //2^3 = 8
parseInt(10000, '2') == Math.pow(2, 4); //2^4 = 16
//and so on
```

So, how to make `10`

, `100`

or `1000`

? Using **shift operations** you can make it:

```
1 << 1 //2
1 << 2 //4
1 << 3 //8
1 << 4 //16
```

A short explanation of above source code is that the binary of `1`

is `00000001`

and when you use left shift operator, the result is `00000010`

, `00000100`

and so on.

So the answer is to use a for-loop for `N`

:

```
var sum = 0;
for (var i = 1;i <= n;i++) {
sum += 1 << i;
}
console.log(sum);
```

## Can we make it better?

Yes. Here is the final hack.

The sum of first N powers of 2 is `2^(N + 1) - 2`

. For instance, `n = 3`

:

```
(2 ^ (3 + 1)) - 2 = 16 - 2 = 2 + 4 + 8 = 14
```

And then, using bitwise operations we have:

```
console.log((2 << n) - 2);
```

Please note that the binary of `2`

is `00000010`

.

Actually, this is the right answer.

Edit: You can find more interesting examples here: http://www.cs.utsa.edu/~wagner/knuth/fasc1a.pdf