乘用算法Bitshifts

在尋找有效的算法用於乘以2個大的數字，在一個論壇上遇到了C以下方法： -乘用算法Bitshifts

... 
    typedef unsigned long long ULL; 

    ULL multiply (ULL a,ULL b) 
    { 
     ULL result = 0; 
     while(a > 0) 
     { 
     if(a & 1) 
     { 
      result += b; 
     } 
     a >>= 1; 
     b <<= 1;  
     } 

     return result; 
    } 
...

上述算法中不需要乘法指令，而使用位位移和只有加法操作（因此使它更快）。

檢查該方法工作正常，但是，我沒有完全知道它是如何工作的。解釋會有幫助。

來源

2016-04-27 Siddhartha Ghosh

請注意一些CPU可以有非常緩慢的移位操作 - 68008曾經是一個例子。所以你的里程可能有所不同 – tofro

「因此使它更快」 - 在一個不是 –

該算法是你在學校長時間乘法學習的相同的東西;除了第一個操作數是以2爲底的。它有時被稱爲「俄羅斯乘法」 –

它遍歷a中的所有1位，並添加b移位適當的數量。

首先，請注意，如果a是11001，它可以作爲10000 + 1000 + 1處理，所以a * b是(10000*b) + (1000*b) + (1*b)。然後，請注意10000*b只是b << 4。

每次通過循環時，b左移1以反映當前移位量，並且a右移1，以便可以測試低位位。在這個例子中，它最終添加了b + (b << 3) + (b << 4)，這只是(1*b) + (1000*b) + (10000*b)。

來源

2016-04-27 04:52:05

哇，這是很好的算法，以及類似於我們做手工：

123* 
456= 
6*(123)+ 
50*(123)+ //this means one digit shift, nice and easy 
400*(123) //this means two digits shift, nice and easy

所以，讓我們做的二進制：

101* //b 
110= //a 
0*(101)+  
10*(101)+ //=1*(1010) //one digit shift 
100*(101) //=1*(10100) //two digits shift

一個右移通過訪問其第一位：if（a & 1）
b左移每個位置做一個數位移動同上

這正是我們做手工乘以當

我建議使用uint64_t中從

#include<stdint.h>

良好而清晰的代碼風格：

#include<stdint.h> 
uint64_t multiply(uint64_t a, uint64_t b) 
{ 
    uint64_t result = 0; 
    while (a > 0) 
    { 
     if (a & 1) 
     { 
      result += b; 
     } 
     a >>= 1; 
     b <<= 1; 
    } 
    return result; 
} 

int main() { 
    uint64_t a = 123; 
    uint64_t b = 456; 
    uint64_t c = multiply(a, b); 
}

來源

2016-04-27 05:52:32

乘用算法Bitshifts

回答

相關問題