剑指offer15_数值的整数次方

数值的整数次方

---

实现函数 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;}
};