剑指 Offer 16. 数值的整数次方——快速幂，栈溢出，阐述java中最小值与最大值的关系

原题链接

问题描述

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

示例 1

输入: 2.00000, 10
输出: 1024.00000

示例 2

输入: 2.10000, 3
输出: 9.26100

示例 3

输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25

说明

-100.0 < x < 100.0
n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。

---

如此简单的一个题目，毫不犹豫地写出了以下代码：

public double myPow(double x, int n) {
    if (n > 0) {
        return pow(x, n);
    } else if (n == 0) {
        return 1;
    } else {
        return pow(1 / x, -n);
    }
}

public double pow(double x, int n) {
    if (n == 1) return x;
    else return x * pow(x, n - 1);
}

其结果

原因在于：

递归调用的次数受到堆栈大小的限制

改进想法：快速幂

public double myPow(double x, int n) {
    if (n >= 0) {
        return pow(x, n);
    }else {
        return pow(1.0 / x, -n);
    }
}

public double pow(double x, int n) {
    if (n == 0) return 1;
    // 如果幂为奇数，提一个x出来
    return (n & 1) == 1 ?  x * pow(x * x, n / 2) : pow(x * x, n / 2);
}

优化一下

public double myPow(double x, int n) {
    if(n == 0) return 1;
    if (n > 0) {
        return (n & 1) == 1 ?  x * myPow(x * x, n / 2) : myPow(x * x, n / 2);
    }else {
        return myPow(1.0 / x, -n);
    }
}

出现结果

原因在于：

Integer.MAX_VALUE == 2147483647

Integer.MIN_VALUE == -2147483647

在java中，Integer.MAX_VALUE + 1 = Integer.MIN_VALUE

所以当n为Integer.MIN_VALUE的时候，取其相反数，还是它自身，所以在递归函数中n一直小于0，造成栈溢出

如何解决？

当n为负，先提一个x出来，修改如下：

因此代码为

public double myPow(double x, int n) {
    if(n == 0) return 1;
    if (n > 0) {
        return (n & 1) == 1 ?  x * myPow(x * x, n / 2) : myPow(x * x, n / 2);
    }else {
        return 1.0 / x * myPow(1.0 / x, -n - 1);
    }
}

其结果：

---

以上是我做题的过程

总结两个解法，都是围绕着快速幂

解法一：递归

思路代码同上

解法二：循环

public double myPow(double x, int n) {
    double result = 1;
    boolean isPositive = n > 0;
    // 考虑特况
    if(n == Integer.MIN_VALUE){
        n = Integer.MAX_VALUE;
        x *= x;
    }
    // 如果n为负数
    n = Math.abs(n);
    while (n > 0){
        if((n & 1) == 1) result *= x;
        // 除以2
        n >>= 1;
        x *= x;
    }
    return isPositive ? result : 1.0 / result;
}