user1043761 - 6 months ago 48

C++ Question

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