快速乘法

快速乘法是采取类似于快速幂的方式计算乘法主要用于计算$$a*b % c$$ (当a*b超过long long的范围时)。

假设$$a=3_{10}=(0011)_2$$

$$b=5_{10}=(0101)_2$$

那么$$a*b=0011 \times 0101=0011 \times 1 + 0110 \times 0 + 1100 \times 1$$

代码:

int_t quickMultiply(int_t a, int_t b) {
    int_t result = 0;
    while (b) {
        if (b & 1) result = result + a;
        a = a << 1;
        b >>= 1;
    }
    return result;
}