迭代对数幂

我最近搞砸了一次采访（使用 collabedit 的电话屏幕）。 这是问题： 编写一个交互式 O(lg n) 算法来求 x^y 的幂（x 是双精度型，y>0 是整数）。

我首先进行了递归分而治之，并尝试将其转换为迭代......但我不能：S 有没有一种方法可以将递归转换为迭代（尾递归很容易，但是具有两个可能的递归调用的递归函数怎么样，这取决于条件来决定将调用哪个调用）？

The typical way to unroll this uses the bitwise representation of b. Compute a¹, a², a⁴, a⁸, etc. and at each step determine whether or not to multiply it into the total. This is shown here:

double result = 1;
double multiplier = a;
for (double multiplier = a; b != 0; multiplier *= multiplier, b /= 2) {
    if (b % 2 == 1) {
       result *= multiplier;
    }
}

For example, to compute 3⁵, we'd notice that 5 has binary representation 101, so we'd multiply in 3¹ and 3⁴.

希望这可以帮助！