实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn ）。此函数应将 x 作为浮点数（意味着它可以是十进制数）和 n 作为整数（可以是正数、负数或零）一起使用。
快速幂（Exponentiation by Squaring） 的时间复杂度是 O(log n)，而不是 O(n)。因此比普通连续相乘的暴力解法快很多，尤其在指数很大时更为明显。
快速幂利用了指数的 二进制分解。关键在于每次指数都除以 2（右移）。
代码：
class Solution {public double myPow(double x, int n) {// If power n is non-negative, calculate power using helper method// 如果指数 n 是非负数，直接调用辅助方法计算if (n >= 0) {return quickPow(x, n);} else {// If power n is negative, calculate the inverse of the power// 如果指数 n 是负数，先转成 long 类型防止溢出，然后计算倒数return 1 / quickPow(x, -(long) n);}}private double quickPow(double base, long exponent) {double result = 1; // Initialize result to neutral element for multiplication// 初始化结果为 1（乘法的单位元）// Loop through all bits of the exponent// 遍历指数的每一位（二进制）while (exponent > 0) {// If the current bit is set, multiply the result by the base// 如果当前位是 1（即指数是奇数），说明该位有效，就把当前 base 乘进结果中if ((exponent & 1) == 1) {result *= base;}// Square the base for the next bit in the exponent// 每处理一位，把 base 平方，指数除以 2，平方乘法base *= base;// Shift exponent to the right to process the next bit// 指数右移一位，继续处理下一个最低位exponent >>= 1;}// Return the final result of base raised to the exponent// 返回最终结果return result;}
}
平方乘法的数学原理
我们知道：
-
x² = x * x -
x⁴ = (x²)² -
x⁸ = (x⁴)²
也就是说：
x^2k = (x^k)^2
这说明：
如果我们每次把底数平方，就相当于一次性“处理了两个幂”。
⛳ 示例过程：a = 2, n = 13
| n | n 的二进制 | 当前位 | result 操作 | base 操作 | 新 result | 新 base |
|---|---|---|---|---|---|---|
| 13 | 1101 | 1 | result *= base | base = base² | 2 | 4 |
| 6 | 0110 | 0 | - | base = base² | 2 | 16 |
| 3 | 0011 | 1 | result *= base | base = base² | 32 | 256 |
| 1 | 0001 | 1 | result *= base | base = base² | 8192 | 65536 |
| 0 | 0000 | - | 结束 |
如果指数 n 是负数，先转成 long 类型防止溢出
Java 中 int 类型的取值范围是：
👉 [-2³¹, 2³¹ - 1]
👉 即 [-2147483648, 2147483647]
int n = Integer.MIN_VALUE; // n = -2147483648
int positive = -n; // 正常来说你想让它变成 2147483648
System.out.println(positive); // 实际输出：-2147483648（依然是负数！）
为什么？因为 2147483648 超出了 int 最大值！
✅ 解决方法：先转成 long
return 1 / quickPow(x, -(long) n);
这样 -(long) n 的计算就不会发生溢出了：
long 是 64 位的，能表示的范围非常大：
-9,223,372,036,854,775,808 到 9,223,372,036,854,775,807
比 int 的表示范围大得多，所以：
long n = Integer.MIN_VALUE; // n = -2147483648 long positive = -n; // 不会溢出 System.out.println(positive); // 输出：2147483648 ✅
🔍 为什么这在快速幂中很重要？
因为我们要把 n 转为正数，才能做快速幂：
如果你不转为 long，那么：
quickPow(x, -n); // 这里 -n 就可能等于 Integer.MIN_VALUE
就会导致逻辑错误甚至死循环（因为指数没变正）。
📘 看一下几个重要值及其补码：
| 十进制值 | 二进制补码表示 | 注释说明 |
|---|---|---|
-2147483648 | 10000000 00000000 00000000 00000000 | 最小的 int，符号位为 1，其他全 0 |
-2147483647 | 10000000 00000000 00000000 00000001 | 第二小，最低位是 1 |
-1 | 11111111 11111111 11111111 11111111 | 补码中所有位都是 1 |
0 | 00000000 00000000 00000000 00000000 | 全 0 |
1 | 00000000 00000000 00000000 00000001 | 正数，从 1 开始递增 |
2147483647 | 01111111 11111111 11111111 11111111 | int 能表示的最大值 |
补码的优点：正负数加法可以统一处理（硬件电路简单）
为什么溢出会“绕回原值”？
Java 中的 int 是固定长度的 32 位，有符号整数。
当你进行超出范围的计算时，多出来的部分会被截断，留下的低 32 位成为新的值。
这就像一个指针在一个圆圈里走路，走过最大值后，就绕到了最小值。
为什么右移？
因为在快速幂算法中，我们是从低位（最右边）开始处理二进制位的，所以需要不断右移指数，把最低位移出去，这样我们就能一位一位检查该不该乘上当前的 base。
-
右移一位（>> 1）：相当于除以 2 向下取整
-
左移一位（<< 1）：相当于乘以 2
我们在快速幂中需要不断除以 2，是为了把 exponent 处理完（直到它变成 0）。
