pow(x，n)的迭代实现

Question

我发现了pow（x，n）的迭代实现，它占用o（logn）时间和常量空间，如下所示：

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的符号来处理负指数，而不是通过减去一从pow（）函数中提取x^1，

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

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

if (!n) return 1;

while循环在将指数n除以2时重复对x进行平方运算（请参见left=x；left=left*left；）。右侧因子用于在设置时计算第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*（i-n））。