寻找幂的算法，即n^p

Question

寻找幂的算法，即n^p

4

求解 n^p 的算法如下：

unsigned long long power(unsigned n, unsigned p)
{
    unsigned long long x=1, y=n;
    while(p > 0)
    {
        if(p&1) x *= y;
        y *= y;
        p >>= 1;
    }
    return x;
}

有人能解释一下这个算法背后的逻辑/数学原理吗？我知道它可以工作并已经对几个测试案例进行了演示。我的意思是，它的工作原理是什么，相较于一般的朴素方法，它为何效率更高。

- gopi1410

1

这是O(log n)，相比于朴素方法的O(n)。它将在每次迭代中将指数减半。 - nhahtdh

1

为什么不在每次迭代中printf x、y和p呢？这将很容易帮助您理解。该代码基本上会遍历p的各个位，而不是运行i=0到p的循环。 - anishsane

Gopi，你应该尝试在循环中打印每个变量，然后你就会知道如何使用1位移位运算符进行更改...并且结果形成在x中。 - Anoop Vaidya

@AnoopVaidya 已经预见到了这一点。无论如何，谢谢，我明白了；我看到我很傻。 - gopi1410

1

顺便说一句，算法加1分...我之前不知道这个算法。读完后似乎很容易 :-) - anishsane

显示剩余2条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Sergey Kalinichenko · Accepted Answer

这是平方求幂法： >>= 1 是写成 /=2 的花式方法。

其背后的思路是，如果 p 是偶数，你可以取 n^(p/2) 然后将其平方；当 p 是奇数时，p-1 必须是偶数，所以你可以取 n^((p-1)/2)，将其平方，然后将结果乘以 n 来补偿在平方之前从 p 中减去的 1。