《剑指offer第二版》题16：数值的整数次方

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

解题思路

最直接的解法就是base乘exponent次，考虑好边界值。

public static double power(double base, int exponent) {
        if (base == 0 && exponent < 0) {
            throw new IllegalArgumentException("Invalid input,base is zero and exponent less than zero.");
        }
        //指数为0,就返回1.
        if (exponent == 0) {
            return 1;
        }
        //求指数的绝对值
        long exp = exponent;
        if (exponent < 0) {
            exp = -exp;
        }
        //真正的算法
        double result = powerWithUnsignedExponent(base, exp);
        if (exponent < 0) {
            result = 1 / result;
        }
        return result;
    }

最直接的方法，最直接的解法就是base乘exponent次。

private static double powerWithUnsignedExponent(double base, long exp) {

    double result = 1.0;
    for (int i = 1; i <= exp; i++) {
        result *= base;
    }
    return result;
}

另一种思路

比如我们要求一个数字的32次方，如果我们已经知道了它的16次方，那么只有在16次方的基础上再平方一次就可以了。而16次方式8次方的平方。这样以此类推，我们求32次方只需要做5次乘法（先求平方、4次方、8次方、16次方，32次方）。我们有如下公式。

我们可以使用递归来实现这个公式。

private static double powerWithUnsignedExponent(double base, long exp) {
    if (exp == 0) {
        return 1;
    }
    if (exp == 1) {
        return base;
    }
    double result = powerWithUnsignedExponent(base, exp >> 1);
    result *= result;
    //如果指数是奇数，就还要乘以一次底数。
    if (exp % 2 != 0) {
        result *= base;
    }
    return result;
}

测试用例

public static void main(String[] args) {

    System.out.println(power(3, 3));
    System.out.println(power(0, 3));
    System.out.println(power(0, 0));
    System.out.println(power(0, 1));
    System.out.println(power(2, -2));
    System.out.println(power(-2, -2));
}

输出结果

27
0
1
0
0
0