iteration - 计算能力的迭代解决方案

Question

我正在开发一种有效的迭代代码来计算 m ⁿ。经过一番思考和谷歌搜索，我找到了这段代码；

public static int power(int n, int m)
// Efficiently calculates m to the power of n iteratively
{
int pow=m, acc=1, count=n;
while(count!=0)
{
 if(count%2==1)
    acc=acc*pow;
 pow=pow*pow;
 count=count/2;
}
return acc;
}

这个逻辑对我来说是有意义的，除了为什么我们pow每次都在接近结束时对值进行平方。我熟悉类似的递归方法，但这种平方对我来说并不是很直观。我可以帮帮她吗？一个带有解释的例子将非常有帮助。

标签： iterationexponentiation

Answer 1

每次迭代都会对累加器进行平方，因为count（这是逆累积功率）每次迭代都会减半。

如果计数为奇数，则累加器乘以该数字。该算法依赖于整数运算，它丢弃除法的小数部分，当计数为奇数时有效地进一步递减 1。