user1043761 user1043761 - 1 month ago 18
C++ Question

Efficient power of 2 series: (2^n) + (2^(n-1)) + (2^(n-2))

I'm wondering if there is a constant time algorithm or some kind of x86 intrinsic for calculating this:

Given 'n', calculate the sum of the series of powers of 2 from 'n to 0':

2^n + 2^(n-1) + 2^(n-2) + 2^(n-3) ... 2^(0)

Answer

The result of a geometric serie like k^n + k^(n-1) + k^(n-2) + k^(n-3) ... k^(0) is (k^(n+1) - 1)/(k-1).

If k=2, this is even simpler: result is 2^(n+1) - 1; and it is used very often.

You can compute it in constant time with left shift operations like

(1U << (n+1)) - 1

or

~(~0U << n)