c++ - 2系高效电源 : (2^n) + (2^(n-1)) + (2^(n-2))

Question

我想知道是否有一个常数时间算法或某种 x86 内在函数来计算这个:

给定'n'，计算从'n到0'的2的幂级数的和:

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

Answer 1

像 k^n + k^(n-1) + k^(n-2) + k^(n-3) ... k^(0) 这样的几何序列的结果是 (k^( n+1) - 1)/(k-1).

如果k=2，这就更简单了:结果是2^(n+1) - 1；并且经常被使用。

你可以用像这样的左移操作在常数时间内计算它

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

或

~(~0U << n)