50. Pow(x, n)

,

Recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public double myPow(double x, int n) {
        if (n == 0) {
            return 1;
        }
        if (n < 0) {
            if (n == Integer.MIN_VALUE) {
                return myPow(1 / (x * x), Integer.MAX_VALUE);
            } else {
                return myPow(1 / x, -n);
            }
        }
        if ((n & 1) == 1) {
            return x * myPow(x * x, n / 2);
        } else {
            return myPow(x * x, n / 2);
        }
    }
}

Iterate

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public double myPow(double x, int n) {
        if (n == 0) {
            return 1;
        }

        long power = n;
        if (n < 0) {
            x = 1 / x;
            power = -power; // 注意此处的越界问题，如果使用 power = -n 会导致符号反转不生效，因为当 n = -2147483648 时，-n 等于 n
        }

        double res = 1;
        while (power > 0) {
            if ((power & 1) == 1) {
                res *= x; // 注意此处是乘以 x
            }

            x *= x;
            power /= 2;
        }

        return res;
    }
}

References

50. Pow(x, n)
剑指 Offer 16. 数值的整数次方
Math.abs returns wrong value for Integer.Min_VALUE - Stack Overflow