迭代对数指数运算

Question

我最近参加了一次面试（使用Collabedit进行电话面试），但是表现不佳。以下是问题：

编写一个 O(lg n) 迭代算法，用于查找 x^y 的值 (x 是 double 类型，y>0 是 int 类型)。

我首先尝试了递归分治方法，并尝试将其转换为迭代方法……但是我做不到:S 是否有一种方法可以将递归方法转换为迭代方法呢？（对于尾递归非常容易，但如果递归函数有两个可能的递归调用，这取决于条件来决定哪个调用将被调用）

- user87219

Answer 1

典型的展开方式使用b的位表示。计算a的1次方，2次方，4次方，8次方等，并在每个步骤中确定是否将其乘入总数中。代码如下：

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

例如，要计算3⁵，我们会注意到数字5的二进制表示为101，因此我们将3¹和3⁴相乘。

希望这可以帮助到您！

- templatetypedef