【計算機組織與結構】二進制乘法那些事(無號數/有號數/Booth/Bit-pair)

今天來玩二進制的乘法吧,想到什麼寫什麼。

無號數的乘法

直式乘法

最基本就是直接使用直式將兩數相乘:

[4bit] 6*3 = 18
(轉換為二進位 0110 * 0011)
因為是4bit相乘,最終結果要延伸位元至8bit

左移位元

當然,電腦總不可能用直式來做乘法運算吧?所以還有一種方法是使用左移位元來做運算,也是電腦採取的運算方式。

取最接近乘數的2的次方數,例如:6*13 = 6*8 + 6*4 + 6*1
這裡的8 , 4 , 1為2^3 , 2^2 , 2^0,代表左移3位,左移2位,左移0位

0110(000)+0110(00)+0110 = 1001110

可以用直式驗證一下答案是否相同

有號數的乘法

將負數取2補數

最基本的有號數相乘為將負數取2補數再來做計算,如(-4)*6 , 2’s

-4 = 1100 , 6 = 0110

將-4取二補數為 1100 => 0011+1 = 0100

兩個4bit整數相乘得到的結果應為8bit,因此延伸位元至8bit = 00011000

最後的結果需要再取二補數,所以答案為11101000。


這樣有一個弊端,當兩數皆為有號數時該如何計算呢?

如:(-2)*(-3) = 6 [2’s],1110*1101取二補數計算卻沒辦法等於+6。

算出來的結果應該要是正的,但是答案卻是負的,想都不用想肯定是錯的。

所以可以使用Booth’s Algorithm來做運算。

Booth’s Algorithm

我之前發的文章有比較詳細的說明布斯乘法的運算方式:Booth’s Algorithm布斯乘法算法

那這邊我就不提該怎麼做計算,直接把剛剛 -2 * -3的題目使用Booth’s Algorithm來計算:

[8bit and 2’s] (-2)*(-3) = 1110 * 1101

因為是8bit,所以將1110延伸為11111110;將1101延伸為11111101

=> 11111110 * 11111101

因為兩個8bit相乘,所以答案為16bit。

負數延伸位元為1,正數延伸位元為0,延伸至16bit
N = (11111111)11111110
-N = (00000000)00000010 [取N的二補數]

最終結果為 6。

如此一來就能確保兩個有號整數相乘時答案是正確的。


還有一個需要提到的是bit-pair recording

乘上題,將轉換後的0 0 0 0 0 -1 +1 -1 相鄰兩個一組做比對變為:0 0 -1 +1

Principles of computer architecture - arithmetic

計算後與剛剛的答案相同:

要注意的是bit-pair有可能會轉換到+2,-2
而+2,-2與+1,-1 位移的位數不同,很可能會計算錯誤,這邊舉一個例子:

[8bit and 2’s] 62*(-29) = 00111110 * 11100011

N = 0000000000111110
-N = 1111111111000010

00 -10 01 0-1做bit-pair => 0 -2 1 -1

最後更新時間:

相關文章

發表留言