pow(x, n)的迭代实现

Question

我找到了 pow(x, n) 的迭代实现，它需要 o(log n) 时间和常量空间，如下所示：

double pow(double x, int n) {
    double left = x;
    double right = 1;

    if (n<0) return 1/(x*pow(x,-n-1)); // Avoid binary overflow!!!!

    if (!n) return 1;

    while (n>1)
    {
        if (n%2==1) right *= left;
        left = left * left;
        n = n/2;
    }

    return left * right;
}

但是我找不到这个算法的任何解释。我理解使用分而治之技术的递归解决方案，我猜这个解决方案使用了类似的技巧。但我不明白为什么会这样。任何人都可以向我解释这个算法吗？谢谢！

Answer 1

该算法将指数 n 分解为表示数字的位。

第一行通过计算倒数和反转 n 的符号来处理负指数。并不是说它通过减去 1 从 pow() 函数中取出 x^1，

if (n<0) return 1/(x*pow(x,-n-1));

该算法通过观察 x^0 = 1 来处理零位（请参阅此行）：

if (!n) return 1;

while 循环重复平方 x（参见 left=x; left = left*left;），因为它将指数 n 除以 2。正确的因子用于在设置时计算第 i 位的值。

while (n>1)
{
    if (n%2==1) right *= left;
    left = left * left;
    n = n/2;
}

当 n<=1 时循环终止，此时第 i 位的值 left == x^(2*i)，而 right == x^(2*(i-1)) + ... x^(2*(in))，对于“开启”的位。