快速乘（俄罗斯农民乘法）

算法原理

先看看我们笔算乘法是怎么计算的：

   88
x  99
----------
  792
+792
----------
 8712

这个过程可以用公式表达为：

88 * 99 = 88 * 9 * 10^0 + 88 * 9 * 10^1
        = 792 + 7920
        = 8712

根据这个原理，我们把第二个乘数换成二进制：

88 * 0110 0011(2) = 88 * 0 * 2^7 
                  + 88 * 1 * 2^6 
                  + 88 * 1 * 2^5 
                  + 88 * 0 * 2^4 
                  + 88 * 0 * 2^3 
                  + 88 * 0 * 2^2 
                  + 88 * 1 * 2^1
                  + 88 * 1 * 2^0

算法用途

通常用在大数相乘取模的情况，可以防止大数相乘溢出。
当我们使用 int类型做快速乘运算时就相当于模2^32（假设 int类型是 4位）。

代码实现

int quickMulti(int A, int B) {
    int ans = 0;
    for ( ; B; B >>= 1) {
        if (B & 1) {
            ans += A;
        }
        A <<= 1;
    }
    return ans;
}

// 作者：LeetCode-Solution
// 链接：https://leetcode-cn.com/problems/qiu-12n-lcof/solution/qiu-12n-by-leetcode-solution/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。