快速求幂

快速求幂

快速幂和快速乘法都是利用了二进制的思想，时间复杂度为O(logN)级别的算法。

算法有两大优点：①便于取模操作（避免溢出） ②时间复杂度较低

public class Main {

    public static void main(String[] args) {
        System.out.println(myPow(3.0, 3));
    }

    public static double myPow(double x, int n){
        double ans = 1;
        while (n > 0){
            if((n & 1) == 1){
                ans *= x;
            }
            x *= x;
            n = n >> 1;
        }
        return ans;
    }
}

public class Main {
    public static void main(String[] args) {
        System.out.println(myPow(3.0, 3));
    }
    public static double myPow(double x, int n){
        if(x == 0.0 || n == 0){
            return 1.0;
        }
        if(n == 1){
            return x;
        }
        double half = myPow(x, n/2);
        if(n % 2 == 0){
            return half * half;
        }else{
            return half * half * x;
        }
    }
}