编程

快速乘法和快速幂

快速乘法

对于 a * b 通过将 b 转换成二进制表示，将乘法转换成加法和位运算。
如
$$
3 * 5 = 3 * (101) = 3 * (2^0 + 2^2)
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static long quickMultiply(long a, long b) {
    long result = 0;
	
    while (b > 0) {
	    // 末尾为 1 加上当前 a 值，如 3 * (1 + 4)，1部分加到结果上，4进行后续运算
        if ((b & 1) == 1) {
            result += a;
        }

        // 循环进行 a * 2, b / 2
        a <<= 1;
        b >>= 1;
    }

    return result;
}

快速幂

与快速乘法类似，将加操作替换成乘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static long quickPow(long a, long b) {
    long result = 1;

    while (b > 0) {
        if ((b & 1) == 1) {
            result *= a;
        }

        a *= a;
        b >>= 1;
    }

    return result;
}