快速幂

fastCounting.png

运算符解释:
n & 1 == 1 同 n % 2 == 1
n >>= 1 同 n /= 2
推荐用位运算符,详情请自行百度

public class fastCounting {

    public static void main(String[] args) {
        long a , n;                //a为计算的数,n为计算数的幂
        
        //使用递归方式求快速幂
        System.out.println(Method1(-5, 3));
        //使用非递归方式求快速幂
        System.out.println(Method2(5, 3));
    }
    public static long Method1(long a,long n) {
        if(n == 0){
            return 1;
        }
        long x = Method1(a, n/2);
        if((n & 1) == 1){
            return x * x * a;
        }else{
            return x * x; 
        }
        
    }
    public static long Method2(long a,long n) {
        int product = 1;
        
        while(n != 0){
            if((n & 1) == 1){
                product *= a;            //当n为单数时,需要多乘一个a,列9/2 = 4,
            }
            a *= a;                        
            n >>= 1;
        }
        return product;
    }

}
Last modification:March 17th, 2019 at 01:33 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment