16.数值的整数次方 (Medium)*

题目描述*

实现函数 double Power(double base, int exponent)，求 base 的 exponent 次方。不得使用库函数，同时不需要考虑大数问题。

示例*

输入: 2.00000, 10

输出: 1024.00000

输入: 2.00000, -2

输出: 0.25000

说明*

-100.0 < x < 100.0，n 是 32 位有符号整数，其数值范围是 $[−2^{31}, 2^{31} − 1]$ 。

代码*

最简单的就是硬算，需要考虑边界情况。

或者使用快速幂算法，把指数按二进制处理。需要注意浮点数不应该用 == 判等。

硬算快速幂

class Solution {
public:
    double myPow(double x, int n) {
        if(x == -1) {
            if((n & 1) == 0) {
                return 1;
            }else {
                return -1;
            }
        }
        if(x == 1.0) {
            return 1;
        }
        if(n == (signed int)0x80000000) {
            return 0;
        }
        double res = 1;
        if(n > 0) {
            for(int i = 0; i < n; i++) {
                res *= x;
            }
        }else {
            n = -n;
            for(int i = 0; i < n; i++) {
                res *=x;
            }
            res = 1 / res;
        }
        return res;
    }
};

class Solution {
private:
    bool isEqual(double a, double b) {
        return a - b > -1e-6 && a - b < 1e-6;
    }
    inline double fastPow(double x, int n) {
        double res = 1.0;
        while(n) {
            if(n & 1) {
                res *= x;
            }
            x *= x;
            n >>= 1;
        }
        return res;
    }
public:
    double myPow(double x, int n) {
        // 底数是 0
        if(isEqual(x, 0.0)) {
            return 0.0;
        }
        if(isEqual(x, 1.0)) {
            return 1.0;
        }
        if(isEqual(x, -1.0)) {
            return n & 1 ? -1.0 : 1.0;
        }
        if(n == (signed int) 0x80000000) {
            return 0.0;
        }
        int sign = n < 0 ? -1 : 1;
        n *= sign;
        double res = fastPow(x, n);
        if(sign == -1) {
            res = 1.0 / res;
        }
        return res;
    }
};

最后更新: July 23, 2022