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