double pow(double x, int n)

实现该函数需要重点考虑以下两方面问题：

• 时间复杂度
  乘法的开销相对较大，所以在这个问题上，我们可以将时间复杂度等同于乘法运算的次数，应该控制在O(log(n))
• 各种边界条件
  1. x = 0
  2. n = 0
     任何数的0次方都是1，不过0^0有的说是1，有的说无意义
  3. n < 0
  4. n = Integer.MIN_VALUE;
     Integer.MIN_VALUE = 10000000000000000000000000000000 , 最高位是符号位，而计算机取反的运算是-n = ~n + 1, 所以-10000000000000000000000000000000 = 01111111111111111111111111111111 + 1 = 10000000000000000000000000000000，相当于-Integer.MIN_VALUE仍然是Integer.MIN_VALUE。对于这种情况，我们可以考虑采用pow(x, n) = x^(-1) * pow(x, Integer.MIN_VALUE + 1)
  5. 中间结果的浮点数溢出
     如果中间结果溢出了，则继续乘下去也没有意义了，而且会导致结果不正确，溢出后应该立刻返回Double.MAX_VALUE

示例代码

class Pow {
    public static double pow(double x, int n) {
        if (n == 0) {
            // here we also treat 0^0 as 1
            return 1;
        }
        if (n < 0) {
            if (x >= 1.0 / Double.MAX_VALUE || x <= - 1.0 / Double.MAX_VALUE) {
                x = 1.0 / x;
            } else {
                return Double.MAX_VALUE;
            }
            if (n == Integer.MIN_VALUE) {
                return x * pow(x, Math.abs(n + 1));
            } else {
                return pow(x, Math.abs(n));
            }
        } else {
            if (n == 1) {
                return x;
            } else if ( n % 2 == 1) {
                return x * pow(x, n - 1);
            } else {
                double d = pow(x, n / 2);
                return d * d;
            }
        }
    }
    public static double pow2(double x, int n) {
        if (n == 0) {
            // here we also treat 0^0 as 1
            return 1;
        }
        double res = 1.0;
        if (n < 0) {
            if (x >= 1.0 / Double.MAX_VALUE || x <= - 1.0 / Double.MAX_VALUE) {
                x = 1.0 / x;
            } else {
                return Double.MAX_VALUE;
            }
            if (n == Integer.MIN_VALUE) {
                res *= x;
                n++;
            }
        }
        boolean isNeg = false;
        if (n % 2 == 1 && x < 0) {
            isNeg = true;
        }
        n = Math.abs(n);
        x = Math.abs(x);
        while (n > 0) {
            if (n & 0x1 > 0) {
                if (res > Double.MAX_VALUE / x) {
                    return Double.MAX_VALUE;
                }
                res *= x;
            }
            x *= x;
            n >= 1;
        }
        return isNeg ? -res : res;
    }
}

第一种方法利用分治和递归实现了复杂度O(log(n))。第二种方法比较巧妙，借鉴了判断一个二进制整数各个位上含有多少个1的方法，例如x^21 = x^(0x10101) = x^(0x10000) * x^(0x100) * x^(0x1)

参考阅读

LeetCode--50 : pow(x, n)
每日算法之三十九：pow(x, n)