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

69 阅读 0 评论 46 点赞

我是靠谱客的博主舒服导师，这篇文章主要介绍java：循环幂余法和快速幂余法（二分求余法），现在分享给大家，希望可以做个参考。

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

复制代码

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

复制代码

1
2
3
4
5
6
7
8
9
快速幂余法（二分求余法）
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;

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
快速幂余法（转化为位运算）
向下整除 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;
    }