c - 为什么这种幂函数起作用？

Question

res = 1;
for ( i = 1; i <= n; i <<= 1 ) // n = exponent
{
    if ( n & i )
        res *= a; // a = base
    a *= a;
}

这应该是更有效的权力代码，但我不知道为什么会这样。

for() 的第一行没问题，我知道为什么会有 i <<= i。但我不明白该行在哪里: if ( n & i )。我知道它是如何工作的，但我不知道为什么......

Answer 1

假设您有一个无符号数的二进制表示形式。你如何找到十进制表示形式？

让我们举一个简单的四位示例:

N = |   0     |    1    |    0    |    1    |
    -----------------------------------------
    | 2^3 = 8 | 2^2 = 4 | 2^1 = 2 | 2^0 = 1 |
    -----------------------------------------
    |    0    |     4   |    0    |     1   |  N = 4 + 1 = 5

现在，如果每个位的基数不固定为 2，而是前一位的平方，并且将每个位的贡献相乘而不是相加，会发生什么:

N = |   0   |  1  |  0  |  1   |
    ----------------------------
    |   a^8 | a^4 | a^2 |  a^1 |
    ----------------------------
    |   0   | a^4 |  0  |  a^1 |  N = a^4 * a^1 = a^(4+1) = a^5

正如你所看到的，代码计算了a^N