快速求幂算法
本文暂且不考虑int类型长度不够的情况。（此情况可以用取模来解决）
当幂非常非常大的时候，快速求幂算法可以迅速的算出结果。
一般情况下，用循环的方式来求幂，时间复杂度非常高（为O(n)），就是因为当指数n非常大的时候，需要执行的循环次数也非常大。所以快速求幂算法的核心思想就是把指数分成两部分，而偶次幂的底数做平方运算。这样不仅能把非常大的指数给不断变小，而且能把所需要执行的循环次数也相应变小。4 ^ 10 = 4 * 4 * 4 * 4 * 4 * 4 * 4 * 4 * 4 * 4
4 ^ 10 = 16 ^ 5
4 ^ 10 = (16 ^ 4) * (16 ^ 1)
4 ^ 10 = (256 ^ 2) * (16 ^ 1)
4 ^ 10 = (65536 ^ 1) ^ (16 ^ 1)
4 ^ 10 = 65536 * 16
我们能够发现，最后的结果是65536 * 16，
而16是怎么产生的？是不是当指数为奇数5时，此时底数为16。
那65536又是怎么产生的呢？是不是当指数为奇数1时，此时的底数为65536。
所以我们能发现一个规律：最后求出的幂结果实际上就是在分解指数的过程中，所有当指数为奇数时底数的乘积。
贴上代码：
public class Solution {
public double Power(double base, int exponent) {
if (exponent == 0) {
return 1;
}
if (base == 0 && exponent < 0) {
throw new RuntimeException("分母不能为0");
}
boolean isNegative = false;
if (exponent < 0) {
isNegative = true;
exponent = -exponent;
}
double result = 1;
while (exponent > 0) {
if (exponent % 2 == 1) {
result *= base;
}
base *= base;
exponent /= 2;//这个过程中会向0取整。因为exponent是正数，所以相当于先将exponent - 1，再除以2。
}
return isNegative ? 1 / result : result;
}
} 继续优化性能：利用位运算 & 和 >>
public class Solution {
public double Power(double base, int exponent) {
if (exponent == 0) {
return 1;
}
if (base == 0 && exponent < 0) {
throw new RuntimeException("分母不能为0");
}
boolean isNegative = false;
if (exponent < 0) {
isNegative = true;
exponent = -exponent;
}
double result = 1;
while (exponent > 0) {
if ((exponent & 1) == 1) {//满足条件即为奇数
result *= base;
}
base *= base;
exponent >>= 1;//这个过程中会向下取整。因为exponent是正数，所以相当于先将exponent - 1，再除以2。
}
return isNegative ? 1 / result : result;
}
}
参考资料
