题目描述

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

保证base和exponent不同时为0

非递归快速幂

public double Power(double base, int exponent) {
    if (exponent == 0) {
        return 1;
    }
    if (exponent < 0) {//负数次幂
        base = 1.0 / base;
        exponent = -exponent;
    }
    double ans = 1.0, tmpEx = base;
    while (exponent > 0) {
        if ((exponent & 0x01) == 1) {
            ans *= tmpEx;
        }
        tmpEx *= tmpEx;//翻倍
        exponent = exponent >> 1;
    }
    return ans;
}

网上解法

链接：https://www.nowcoder.com/questionTerminal/1a834e5e3e1a4b7ba251417554e07c00?answerType=1&f=discussion
来源：牛客网

预处理：求pow(b, n)，如果n为负数怎么解决？

假如求 $图片说明$ ,是不是可以转换成 $图片说明$
于是，预处理代码如下：

double Power(double b, int n) {
    if (n < 0) {
        b = 1 / b;
        n = -n;
     }
}

方法一：暴力方法

很显然就是n个b相乘。循环n次。

class Solution {
public:
    double Power(double b, int n) {
        if (n < 0) {
            b = 1 / b;
            n = -n;
        }
        double ret = 1.0;
        for (int i=0; i<n; ++i) ret *= b;
        return ret;
    }
};

时间复杂度：O(n)
空间复杂度：O(1)

方法二：递归法（快速幂）

假设我们求 $图片说明$ ，如果我们知道 $图片说明$ ，那么 $图片说明$ ，所以 $图片说明$

但是还有个小问题，如果n是偶数，那么上述没问题。

如果n是奇数， $图片说明$ ，比如 $图片说明$
代码如下：

class Solution {
public:
    double q_power(double b, int n) {
        if (n == 0) return 1.0;
        double ret = q_power(b, n/2);
        if (n&1) { // 奇数
            return ret * ret * b;
        }
        else {
            return ret * ret;
        }
    }
    double Power(double b, int n) {
        if (n < 0) {
            b = 1 / b;
            n = -n;
        }
        return q_power(b, n);
    }
};

时间复杂度：O(logn)，每次规模减少一半
空间复杂度：O(logn)，递归栈，因为要记住logn个变量

方法三：非递归的快速幂

假设求 $图片说明$ ,已知6可以表示成二进制110
可以表示成 $图片说明$ ,所以 $图片说明$ 可以表示成 $图片说明$ 所以，对于二进制数，遇到位数是1的就乘到答案中。
代码如下：

class Solution {
public:

    double Power(double b, int n) {
        if (n < 0) {
            b = 1 / b;
            n = -n;
        }
        double x = b; // 记录x^0, x^1, x^2 ...
        double ret = 1.0;
        while (n) {
            if (n&1) {
                ret *= x; // 二进制位数是1的，乘进答案。
            }
            x *= x;
            n >>= 1;
        }
        return ret;
    }
};

上述方法相当于遍历n的二进制位，是1就乘进结果
时间复杂度：O(logn)，因为n的二进制位个数为logn
空间复杂度：O(1)

拓展

STL标准库中，pow函数的代码如下：

template <class T,class Integer, class MonoidOperation>
T power_this(T x, Integer n, MonoidOperation op){ // 可以看成求pow(x, n)
    if (n == 0)
        return identity_element(op); // 可以看成 1
    else{
        while ((n & 1) == 0){
            n >>= 1;
            x = op(x, x); //op看成乘法
        }
        T result = x; // 遇到 二进制中从低位到高位的第一个 1
        n >>= 1;
        while (n != 0){
            x = op(x, x);
            if ((n & 1) != 0)
                result = op(result, x);
            n >>= 1;
        }
        return result;
    }
}

做法跟我们方法三是一样的。

Eric's Blogs

数值的整数次方