二進制乘法器的C++實現

我正在嘗試一個32位二進制乘法器的C++實現。我知道這樣做是二進制乘法器的C++實現

1011 (this is 11 in decimal)  
x 1110 (this is 14 in decimal)  
    ======   
    0000 (this is 1011 x 0)  
    1011 (this is 1011 x 1, shifted one position to the left)  
    1011  (this is 1011 x 1, shifted two positions to the left)  
1011  (this is 1011 x 1, shifted three positions to the left) 
=========  
10011010 (this is 154 in decimal).

只是其中一種方法是否有另一種方式做到這一點是不那麼繁瑣的代碼，我必須做在較長二進制數的操作？

來源

2013-04-08 user2257566

http://en.wikipedia.org/wiki/Multiplication_ALU#Implementations – 2013-04-08 12:45:58

如果你需要乘以32位數，爲什麼不使用64位類型呢？ – Mikhail 2013-04-08 12:45:59

您可以使用Booth的乘法算法。有維基百科上的更多信息：http://en.wikipedia.org/wiki/Booth%27s_multiplication_algorithm

來源

2013-04-08 12:47:15 OGH

由於用於整型類型的隱式乘法是二進制乘法，可以利用直接治療位數作爲基體2 ，2 或更高，而不是基數2 。

如果您假設8位數字（乘以unsigned char s），下面的24位示例比您的問題中發佈的4位乘法更簡單。

  a1 a2 a3 (this is a 3 byte value)  
     x b1 b2 b3 (this is another 3 byte value)  
      ======   
     xx xx xx xx (this is a x b3)  
    xx xx xx xx  (this is a x b2, shifted 8 bits to the left)  
xx xx xx xx   (this is a x b1, shifted 16 bits to the left) 
=================  
xx xx xx xx xx xx (this is the result).

可以在上面short或long替換「字節」，用位移相應的調整。

只要確保將被乘數轉換爲足夠大的類型以容納乘以之前的進位即可。

來源

2013-04-08 12:55:19

一般情況下，乘以3位數的整數時，產品中應該有6位數字。 – 2013-04-08 12:59:05

3位數整數乘以1位整數給出4位數的整數，因此，中間結果也更長，並且應該有3位整數，而不是4. – 2013-04-08 13:07:31

@AlexeyFrunze我編輯了此可視化回答不再稱這些數字爲「carry」。希望這會更清楚。 – 2013-04-08 13:16:18

是的，你可以通過使用循環來完成這一點。假設類型long是32位，所以long * long的結果是64位。

例如，如果你有一個long A螞蟻一個long B，而要計算a*b

首先，定義結果作爲long long result = 0;。然後檢查B的每一位，如果位是1，則添加A << X以得出結果。其中X是位的索引。一個循環可以實現這一點。

long long AA = A;// convernt A to AA to avoid overflow 
for(int index=0;i<32;++index) 
{ 
    if(B & 0x1) 
     result += AA; 
    AA <<= 1; 
    B >>= 1; 
}

我希望我沒有犯錯，這個想法可以幫助你。

來源

2013-04-08 13:11:46

那麼，（正確和有效的）實現任意精度和大數是繁瑣以及在生產代碼中使用它通常善意的提醒到，而使用一個測試框架（例如，boost，gmp等）。但是，如果你自己實現它，我不會將該數字作爲一系列位存儲，而是作爲一系列機器字（如unsigned int）來充分利用您的硬件ALU功能。所以每個單詞已經代表了許多位，你的ALU知道如何將這些位相乘。

請注意，當您將一個數字與n數字（基數無關）相乘時，您將得到一個數字爲2n的數字，例如， 99 * 99 = 9801（基數10），0xFF * 0xFF = 0xFE01（基數16）。因此，如果您的系統上的std::uintmax_t爲std::uint64_t，則可以將您的號碼存儲爲std::uint32_t的一個序列。當乘以兩位數字時，將它們轉換成std::uint64_t並將它們相乘。高32位將成爲下一個更高位數的乘法部分。（其實，你也可以直接乘std::uintmax_t變量，但得到的結果的高位部分通常是一個有點棘手，涉及以訪問根據寄存器內聯彙編。）

有了這些知識的school multiplication method實施應該是直截了當的：只要迭代編號爲a的所有數字a[i]，並將每個數字乘以b（不要忘記傳播進位）。將結果向上移動i數字，並將所有內容添加到最終結果中。

注意，該算法在原始乘法次數方面具有二次複雜性。如果你有（非常非常大）的數字，你也可以切換到更復雜的方法，如Karatsuba甚至FFT和Schönhage-Strassen。但在這種情況下，我真的推薦使用庫來代替。

來源

2013-04-08 13:53:34

二進制乘法器的C++實現

回答

相關問題