算法原理

先看看我們筆算乘法是怎么計算的：

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

這個過程可以用公式表達為：

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

根據(jù)這個原理，我們把第二個乘數(shù)換成二進制：

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

算法用途

通常用在大數(shù)相乘取模的情況，可以防止大數(shù)相乘溢出。
當(dāng)我們使用 int類型做快速乘運算時就相當(dāng)于模2^32（假設(shè) int類型是 4位）。

代碼實現(xiàn)

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）
// 著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。