题目描述

实现 pow(x, n) ，即计算 x 的 n 次幂函数。

样例1

输入: 2.00000, 10
输出: 1024.00000

样例2

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

算法1

(快速幂的递归写法) $O(logn)$

• 每次把数字缩小一半再相乘

• n为偶数：$3^{20}=3^{10}·3^{10}$

• n为奇数：$3^{21}=3^{10}·3^{10}·3^1$
• 注意：负数且为奇数，>>1结果并不是除2，例如-5>>1=-3，且-1>>1=-1，所以递归到-1需要返回，否则栈会溢出
• 所以$3^{-5}=3^{-3}·3^{-3}*3$

Java 代码

class Solution {
    //递归法：分治
    public double myPow(double x, int n) {
        if(n == 0) return 1;
        if(n == -1) return 1/x;
        double half = myPow(x,n>>1);
        half *= half;
        return (n & 1) == 1 ? half*x : half;
    }
}

算法2

(快速幂的非递归写法) $O(logn)$

• $21=(10101)2$
• $3^{21}=3^{1·2^{4}}·3^{0·2^{3}}·3^{1·2^{2}}·3^{0·2^{1}}·3^{1·2^{0}}$
• $3^{2^0}=3$，所以$3^2$，$3^4$可以依次由前面平方计算得出，并且在计算的过程中，判断每一位二进制位，决定是否将某一项加入结果中
• 注意：n为负数先转为正数，最后再取倒数。整型最小值取反会越溢出，需要转换为long类型

Java 代码

class Solution {
    public double myPow(double x, int n) {
        double res = 1.0;
        boolean isMinus = n < 0 ? true : false;
        long m = isMinus ? -((long)n) : n;
        while(m > 0){
            if((m & 1) == 1) res *= x;
            x *= x;
            m >>= 1;
        }
        return isMinus ? 1/res : res;
    }
}