Java数据结构之快速幂的实现

简介

快速幂算法是计算 a 的 n 次方时经常使用的一种算法，其时间复杂度为 O(logn)，相比直接计算 a^n 的时间复杂度 O(n) 要更加高效。

实现过程

public class FastPower {

    /**
     * 快速幂算法
     *
     * @param base     底数
     * @param exponent 指数
     * @param modulus  取模数
     * @return 计算结果
     */
    public static long fastPower(long base, long exponent, long modulus) {
        long result = 1;
        while (exponent > 0) {
            if ((exponent & 1) == 1) {
                result = (result * base) % modulus;
            }
            base = (base * base) % modulus;
            exponent >>= 1;
        }
        return result;
    }
}

上述代码实现了一个快速幂算法的静态方法 fastPower。其中，base 表示底数，exponent 表示幂，modulus 表示取模数。实现过程如下：

1. 初始化 result 为 1。
2. 当 exponent 大于 0 时，进入循环。
3. 如果 exponent 的最后一位是 1（即 exponent & 1 == 1），则将 result 乘以 base 并对 modulus 取余。
4. 将 base 的值平方，并对 modulus 取余。
5. 将 exponent 右移一位（即除以 2）。
6. 重复第 2 步至第 5 步，直至 exponent 的值变为 0。
7. 返回 result。

示例说明

示例一

计算 2 的 10 次方对 1000000007 取模的结果。

long result = FastPower.fastPower(2, 10, 1000000007);
System.out.println(result); // 输出结果为 1024

首先，我们初始化 base 为 2，exponent 为 10，modulus 为 1000000007，然后进入循环：

exponent	base	result
10	2	1
5	4	1
2	16	4
1	256	4
0	65536	1024

最终得出 2 的 10 次方对 1000000007 取模的结果为 1024。

示例二

计算 7 的 37 次方对 13 取模的结果。

long result = FastPower.fastPower(7, 37, 13);
System.out.println(result); // 输出结果为 9

初始化 base 为 7，exponent 为 37，modulus 为 13，然后进入循环：

exponent	base	result
37	7	1
18	10	7
9	9	0
4	3	0
2	9	0
1	3	0
0	1	9

最终得出 7 的 37 次方对 13 取模的结果为 9。