题目：

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

这个问题最简单的方法是暴力求解，循环exponent次，每次乘于base，最终结果即为所求。注意负数，代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    public double Power(double base, int exponent) {
        if (base == 0.0) {
            return 0;
        }
        if (exponent == 0) {
            return 1;
        }
        double res = 1;
        int minus = exponent > 0 ? 1 : -1;
        exponent = exponent > 0 ? exponent : -exponent;
        while (exponent > 0) {
            res *= base;
            exponent --;
        }
        return minus > 0 ? res : 1 / res;
    }
}

时间复杂度是O(n)。当然这种思路并不高效，做了很多重复工作。比如a^32完全可以由a^16平方得到，a^16可以由a^8平方得到，以此类推直到a^1；而奇数情况下则只需要再乘一次a即可。而由这个思路则可以得到如下打码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    public double Power(double base, int exponent) {
        if (base == 0.0) {
            return 0;
        }
        if (exponent == 0) {
            return 1;
        }
        double res = base;
        int minus = exponent > 0 ? 1 : -1;
        exponent = exponent > 0 ? exponent : -exponent;
        int ex = exponent;
        while (ex = ex >> 1) {
            res *= res
        }
        if(exponent & 1 == 1) {
            res *= base;
        }
        return minus > 0 ? res : 1 / res;
    }
}

这种思路的时间复杂度是O(logn)，相比第一种解法简单了很多。