核心思想：每次迭代都尽可能的将指数减半，来有效减小底数相乘的次数。
传统的幂运算pow(x, y)过程为进行y次乘x运算。
如果一个幂运算的值数太大，传统的求幂运算会进行大量的循环，效率很低。
快速幂核心思想是每一次都将指数分成两半，而相应的底数做平方运算。这能有效的将指数快速变小，需要执行的循环次数也大大减小。
对于一个幂运算pow(3, 10)
一开始的计算方式为pow(3, 10)
经过一次快速幂处理，指数减半底数平方，变成了
pow(9, 5)
现在指数变成了一个奇数，不能直接平分，我们拿出一个1来，剩下的部分变成了偶数4，也就是
pow(9, 4) * pow(9, 1)
而对前面这一部分可以进行一次快速幂处理，现在就变成了
pow(81, 2) * pow(9, 1)
再对pow(81, 2)进行快速幂处理，最终变成了
pow(6561, 1) * pow(9, 1)
我们可以发现，在进行快速幂处理的时候，如果指数为偶数，可以直接进行处理，如果指数为奇数，我们可以将指数拆分为1和一个偶数，其中指数为1的部分就不用再进行处理了。对于指数为偶数的部分可以继续进行快速幂处理，直到所有的指数都变成了1，也就无法再进行快速幂处理了。所有的指数为1的幂运算相乘即为最终的结果。
示例代码：
//非递归版本
double fastPow(double x, int n) {
double res = 1;
while(n>0) {
//当指数为奇数时，可以拆分出一个指数为1的幂运算，我们直接将其乘到res即可
if(n&1) {
res *= x;
}
//底数平方
x *= x;
//指数右移一位（如果原本为奇数，那这个效果相当于-1并除2）
n >>= 1;
}
return res;
}
//递归版本
double fastPow(double x, int n) {
if(n == 0) {
return 1;
}
//底数平方,指数右移一位（如果原本为奇数，那这个效果相当于-1并除2）,并且如果原本的指数为奇数，还要再乘x，否则乘1
return fastPow(x*x, n>>1) * (n&1 == 1 ? x : 1);
}
Original: https://www.cnblogs.com/shiruyanhai/p/16387469.html
Author: 诗如沿海
Title: 快速幂
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/608657/
转载文章受原作者版权保护。转载请注明原作者出处！