算法之数字运算

一、快速幂

（1）普通算法：求a^b%m的时间复杂度为O(b)

（2）快速幂：求a^b%m的时间复杂度为O(logb)

　　比喻：我们已知 2^3  求 2^6,不就是 2^3 * 2^3嘛。快速幂就是这个原理；当遇到奇数时2 ^ 5，就是 2 * 2 ^ 4 。

　　求a ^ b快速幂的基本思路：

　　　　1）当b是奇数时，那么有 a^b = a * a^*(b-1)

　　　　2）当b是偶数时，那么有 a^b = a^(b/2) * a^(b/2)

　　　　如：2^10 = 2^5 * 2^5

　　　　　　2^5 = 2 * 2^4

　　　　　　2^4 = 2^2 * 2^2

　　　　　　2^1 = 2 * 2^0

　　求 a^b%m

//暗指int为长整型
public int fun(int a,int b,int m){
    int ans=1;
    while(b>0){
        //位与&运算要比%运算要快  
        if(1==(b&1)){
            ans=ans*a%2;
        }
        a=a*a%2;
        b=b>>1;
    }
    return ans;
}

二、java的左移与右移

　　左移代表乘，左移一位代表乘2,左移两位代表乘4，依次递增           12<<1=24    12<<2=48 

　　右移代表除,  右移一位代表除2,右移两位代表除4，依次递增            12>>1=6      12>>2=3

　　System.out.println(12>>2)//结果为3

　　System.out.println(12<<1)//结果为1

算法之数字运算

原文：https://www.cnblogs.com/hdc520/p/12554989.html