實現?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;}
}
平方乘法的數學原理
我們知道：
-
x2 = x * x -
x? = (x2)2 -
x? = (x?)2
也就是說：
x^2k = (x^k)^2
這說明：
如果我們每次把底數平方，就相當于一次性“處理了兩個冪”。
? 示例過程：a = 2, n = 13
| n | n 的二進制 | 當前位 | result 操作 | base 操作 | 新 result | 新 base |
|---|---|---|---|---|---|---|
| 13 | 1101 | 1 | result *= base | base = base2 | 2 | 4 |
| 6 | 0110 | 0 | - | base = base2 | 2 | 16 |
| 3 | 0011 | 1 | result *= base | base = base2 | 32 | 256 |
| 1 | 0001 | 1 | result *= base | base = base2 | 8192 | 65536 |
| 0 | 0000 | - | 結束 |
如果指數 n 是負數，先轉成 long 類型防止溢出?
Java 中 int 類型的取值范圍是：
👉 [-231, 231?-?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）。
