Algo寻找力量即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在平方之前减去的数.