AcWing刷题笔记-27-数值的整数次方

题目描述

实现函数 double Power(double base, int exponent)，求 base 的 exponent 次方。

不得使用库函数，同时不需要考虑大数问题。

初步思路

第一眼看上去很简单，不就是循环乘 exponent 次嘛。但仔细一想，exponent 可能是负数，而且数据范围很大时，暴力 O(n) 会超时。所以这道题真正的考点是快速幂。

另外还有一个坑：exponent 是 int 类型，当它为 INT_MIN（-2147483648）时，直接取负会溢出。所以必须先转成 long long 再处理。

算法分析

方法一：暴力遍历

循环 abs(exponent) 次，逐次相乘。
时间复杂度：O(n)，会超时。
代码略（仅作为对比）。

方法二：快速幂（递归）

核心思想：利用二分思想，base^exp = base^(exp/2) * base^(exp/2)（exp 为偶数），奇数则再多乘一个 base。
时间复杂度：O(log n)。
需要注意递归终止条件和 exponent 为负的情况。

方法三：快速幂（迭代/位运算）

核心思想：将指数 exp 拆成二进制形式，从低位到高位逐位判断。如果当前位为 1，就将对应的 base 幂乘入结果。
例如：3^13 = 3^(1101)_2 = 3^8 * 3^4 * 3^1。
时间复杂度：O(log n)，空间复杂度 O(1)，比递归版本更优。

代码实现（C++）

暴力遍历

class Solution {
public:
    double Power(double base, int exponent) {
        double res = 1;
        for(int i = 0;i<abs(exponent);++i){
            res*=base;
        }
        if(exponent<0)return 1/res;
        return res;
    }
};

快速幂 + 递归

class Solution {
public:
    double Power(double base, int exponent) {
        if (base == 0) return 0.0;
        if (base == 1 || exponent == 0)
            return 1.0;

        long long exp = exponent;
        if (exp < 0) exp = -exp;

        double res = qpow(base, exp);
        return exponent > 0 ? res : 1 / res;
    }

    double qpow(double base, long long exp) {
        if (exp == 0) return 1.0;

        double half = qpow(base, exp / 2);
        if (exp % 2 == 0)
            return half * half;
        else {
            return half * half * base;
        }
    }
};

快速幂 + 迭代（推荐）

class Solution {
public:
    double Power(double base, int exponent) {
        if (base == 0) return 0.0;
        if (base == 1 || exponent == 0)
            return 1.0;

        long long exp = exponent;
        double res = 1.0;
        if (exp < 0) exp = -exp;

        while (exp) {
            if (exp & 1) res *= base;  // 当前二进制位为 1，乘入结果
            base *= base;               // base 平方，对应下一位的权重
            exp >>= 1;                  // 指数右移一位
        }

        return exponent < 0 ? 1 / res : res;
    }
};

测试用例

输入	输出	说明
`base=2, exponent=10`	`1024`	正指数常规情况
`base=2, exponent=-3`	`0.125`	负指数，先算正指数再取倒数
`base=2, exponent=-2147483648`	`0`	`INT_MIN` 取负会溢出，必须先转 `long long`
`base=0, exponent=5`	`0`	底数为 0

总结与反思

几个很重要的细节：

exponent 必须先转成 long long 再取绝对值。int 类型的最小值是 -2147483648，它的绝对值是 2147483648，已经超出了 int 的最大范围，直接 abs(exponent) 会溢出导致结果错误。
快速幂的核心思想是二进制拆分。把指数看成二进制，每一位对应一个 base 的幂次，通过不断对 base 平方来预处理每一位的权重。
迭代版本比递归版本更优。两者时间复杂度都是 O(log n)，但迭代版本空间复杂度是 O(1)，而且没有递归栈溢出的风险。
边界处理：base == 0、base == 1、exponent == 0 可以提前返回，减少不必要的计算。

这道题也是面试高频题，快速幂的思想在很多场景都会用到（比如矩阵快速幂）。

TK的小站