java：循环幂余法和快速幂余法（二分求余法）

当求解x的a次幂时，可能会出现大数越界的问题，超出int32位，所以很多题目要求对结果进行1000000007的取余，这个数字在int32的范围之内
1000000007的平方超出了int32的范围，但是在long64的范围之内

循环幂余法求解x的a次幂
int res = 1;
int x = 3;
int p = 1000000007;
for(int i = 0; i < a; i++) {
	res = (res * x) % p;
}
return res;
该法时间复杂度为线性级别复杂度

快速幂余法（二分求余法）
int p = 1000000007;
long x = 3, res = 1;
for( int i = a; i > 0; i /= 2) {
	if(i == 1) return rem = (rem * x) % p;
	x = (x * x) % p;
}
return (int)res;

快速幂余法（转化为位运算）
向下整除 n / 2 等价于 右移一位 n>>1 ；
取余数 n%2 等价于 判断二进制最右一位值 n&1 ；
Java 代码中 int32 变量 n∈[−2147483648,2147483647] ，因此当 n=−2147483648 时执行 n=−n 会因
越界而赋值出错。解决方法是先将 n 存入 long 变量 b ，后面用 b 操作即可。
public double myPow(double x, int n) {
        if(x == 0) return 0;
        long b = n;
        double res = 1.0;
        if(b < 0) {
            x = 1 / x;
            b = -b;
        }
        while(b > 0) {
            if((b & 1) == 1) res *= x;
            x *= x;
            b >>= 1;
        }
        return res;
    }

最后

以上就是舒服导师为你收集整理的java：循环幂余法和快速幂余法（二分求余法）的全部内容，希望文章能够帮你解决java：循环幂余法和快速幂余法（二分求余法）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。