數值的整數次方

---

實現函數 double Power(double base, int exponent)

題目要求

計算 ${\text{base}}^{\text{exponent}}$：

• 不得使用庫函數
• 不需要考慮大數問題，絕對誤差不超過 $10^{?2}$
• 不會出現底數和指數同為 0 的情況
• 當底數為 0 時，指數一定為正
• 底數絕對值不超過 10，指數范圍 $[?2^{31},2^{31}?1]$

樣例1

輸入：10 ，2輸出：100

樣例2

輸入：10 ，-2  輸出：0.01

---

算法思路

1. 處理指數為 0 的情況：直接返回 1.0。
2. 處理負指數：
   • 將負指數轉換為正數處理
   • 使用 long long 存儲指數，避免 INT_MIN 取絕對值時溢出
   • 最終結果取倒數
3. 快速冪算法：
   • 初始化結果 res = 1.0
   • 循環處理指數（二進制分解）：
     • 若當前二進制位為 1，則乘上當前底數
     • 底數平方，指數右移一位
   • 若底數變為 0，提前終止循環（避免后續無效計算）
4. 處理負指數結果：返回 1.0/res

時間復雜度

• O(log?n)：每次迭代將指數減半

關鍵點

• 負指數處理：轉換為正數計算后取倒數
• 大指數處理：使用 long long 避免溢出
• 浮點精度：當底數平方下溢為 0 時提前終止
• 邊界情況：底數為 0 時直接返回 0（指數為正）

C++ 實現

class Solution {
public:double Power(double x, int n) {typedef long long ll;double res = 1;bool im = n < 0;for(ll k = abs(ll(n)); k; k >>= 1){if(k & 1) res *= x;x *= x;}if(im) res = 1 / res;return res;}
};