c++ - 寻找功率的算法，即 n^p

Question

寻找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;
}

有人可以解释这个算法背后的逻辑/数学。我知道它可以工作并针对一些测试用例（试运行）进行了解决。我的意思是它是如何工作的，以及这与一般的幼稚方法相比如何有效。

Answer 1

这是通过平方求幂：这>>= 1是一种奇特的书写方式/= 2。

它背后的想法是，如果p是偶数，你可以取n^(p/2)它并平方它；当p是奇数时，p-1必须是偶数，因此您可以取n^((p-1)/2)，对其进行平方，然后将结果乘以n以补偿您在平方之前1减去的结果。p