剑指 Offer 16. 数值的整数次方

LeetCode：剑指 Offer 16. 数值的整数次方

快速幂裸题

1. 指数为负数时，-2^31 取相反数的时候， 会数据溢出， 相应的使用 long 接收。
2. 指数为偶数的时，可以将底数相乘， 指数处以2 来降低幂次
3. 指数为奇数时，将一个底数抽离出来，指数就变成偶数了，再做指数偶数时的运算。

public class Offer16 {


    public double myPow(double x, int n) {
        double res = 1;
        if (n == 0) {
            return res;
        } else if (n > 0) {
            res = reducePower(res, n, x);
        } else if (n < 0) {
            // 指数为负数
            long temp = n; // n 的范围 [-2^31, 2^31 - 1] 防止 n 被 超出类型范围
            temp = temp * (-1);
            res = 1.0 / reducePower(res, temp, x);

        }
        return res;
    }

    public double reducePower(double res, long n, double x) {
        while (n > 1) {
            if ((n & 1) == 1) {
                // 为 1 ，奇数
                res = res * x;
                n--;
            }
            x = x * x;
            n = n >> 1;
        }
        res = res * x;
        return res;
    }


    public static void main(String[] args) {
        Offer16 o = new Offer16();
//        double v = o.myPow(0.00001,
//                2147483647);
        double v = o.myPow(2.00000,
                -2);
        System.out.println(v);
    }

}

---

了解：快速幂算法介绍