快速幂(Exponentiation by squaring)或称：平方求幂，是一种高效计算幂函数的算法。
其以O(logN)的时间复杂度求任意乘方。
本质上，快速幂是分治思想的一种应用。
案例引入
欲求8的6次方
常规算法：
private double pow(double x, int y) {
double result = 1;
for (int i = 0; i < y; i++) {
result *= x;
}
return result;
}
该算法的时间复杂度为O(N)。
从数学推导
数学公式： $$ a ^ n * a ^ n = a ^ {2n} \ a ^ n * a ^ m = a ^ {n + m} $$ 以此作为突破，整理思路。
欲计算 6 次方，则该式简化为： $$ 8 ^ 6 = 8 ^ 3 * 8 ^ 3 ;;;① \ 8 ^ 3 = 8 ^ 2 * 8 ^ 1;;;②\ 8 ^ 2 = 8 ^ 1 * 8 ^ 1;;;③ $$ 根据上述理论，可以写出如下方程式： $$ a ^ n = \left{\begin{matrix} a ^ {n - 1},;;;;;;;; n是奇数\ a ^ \frac{n}{2} * a ^ \frac{n}{2},;;;; n是偶数 \ 1,;;;;;;;;;;;n为0 \end{matrix}\right. $$ 整理为代码：
private double pow(double x, int y) {
if (y == 0) {
return 1;
} else if (y % 2 == 1) {
return pow(x, y - 1) * x;
} else {
double temp = pow(x, y / 1);
return temp * temp;
}
}
其中，利用到了 二分查找 的思想。
递归虽然简洁，但会产生额外的栈空间开销。将递归改写为递推(循环)，来避免对栈空间的大量占用，也就是非递归快速幂。
非递归快速幂
从另一个视角引入快速幂：
已知定理：
任何自然数都可以转化为 2的n次方相乘 。
例：
$$
2023 = (0111; 1110; 0111)_{2} = 2^0+2^1+2^2+2^5+2^6+2^7+2^8+2^9+2^{10}
$$
二进制上从右往左第n位，分别代表2 的 n - 1次方，而所有的数都可以用二进制表示，所以我们可以根据二进制来优化幂的计算。
也就是说，所有的幂计算都可以看作是底数的2的n次方幂相乘。
例如：
$$
3^{999} = 3^{512}+3^{256}+3^{128}+3^{64}+3^{32}+3^{4}+3^{2}+3^{1}
$$
其中 512、256、128、64、32、4、2和1都是 2 的 n 次方。
将以上理论转化为代码可得：
double pow(double x, int y){
double result = 1;
while (y != 0)
{
if ((y & 1) == 1) {
result *= x;
}
y >>= 1;
x *= x;
}
return result;
}
当y < 0时，上述代码存在问题。
则修改为：
public double pow(double x, int y) {
double result = 1.0;
if(y < 0) {
x = 1 / x;
y = -y;
}
while(y > 0) {
if((y & 1) == 1) {
result *= x;
}
x *= x;
y >>= 1;
}
return result;
}