比較好的帶符號數乘法的方法是布斯(Booth)演算法.它採用相加和相減的操作計算補碼資料的乘積.Booth演算法對乘數從低位開始判斷,根據兩個資料位的情況決定進行加法、減法還是僅僅移位操作.判斷的兩個資料位為當前位及其右邊的位(初始時需要增加一個輔助位0),移位操作是向右移動.在上例中,第一次判斷被乘數0110中的最低位0以及右邊的位(輔助位0),得00；所以只進行移位操作；第二次判斷0110中的低兩位,得10,所以作減法操作並移位,這個減法操作相當於減去2a的值；第三次判斷被乘數的中間兩位,得11,於是只作移位操作；第四次判斷0110中的最高兩位,得01,於是作加法操作和移位,這個加法相當於加上8a的值,因為a的值已經左移了三次. 一般而言,設y=y0,yly2…yn為被乘數,x為乘數,yi是a中的第i位(當前位).根據yj與yi+1的值,Booth演算法表示如下表所示,其操作流程如下圖所示.在Booth演算法中,操作的方式取決於表示式(yi+1-yi)的值,這個表示式的值所代表的操作為： 0 無操作 +1 加x -1 減x Booth演算法操作表示 yi yi+1 操作 說明 0 0 無 處於0串中,不需要操作 0 1 加x 1串的結尾 1 0 減x 1串的開始 1 1 無 處於1串中,不需要操作 乘法過程中,被乘數相對於乘積的左移操作可表示為乘以2,每次迴圈中的運算可表示為對於x(yi+1-yi)2^31-i項的加法運算(i=3l,30,…,1,0).這樣,Booth演算法所計算的結果 可表示為： x×(0-y31)×2^0 +x×(y31-y30)×2^1 +x×(y30-y29)×2^2 … [1] +x×(y1-y0)×2^31 =x×(-y0×231 +y1×2^30 +y2×2^29+y31×2^0) =x×y 例：用Booth演算法計算2×(-3). [2]補=0010, [-3]補=1101,在乘法開始之前,R0和R1中的初始值為0000和1101,R2中的值為0010. 在乘法的第一個迴圈中,判斷R1的最低位和輔助位為10,所以進入步驟1c,將R0的值減去R2的值,結果1110送人R0,然後進入第二步,將R0和Rl右移一位,R0和R1的結果為11110110,輔助位為l. 在第二個迴圈中,首先判斷Rl的最低位和輔助位為0l,所以進入步驟1b,作加法,R0+R2=1111+0010,結果0001送入R0,這時R0R1的內容為0001 0110,在第二步右移後變為0000 1011,輔助位為0. 在第三次迴圈中,判斷位為10,進入步驟lc,R0減去R2,結果1110送入R0,R1不變；步驟2移位後R0和R1的內容為1111 01011,輔助位為1. 第四次迴圈時,因兩個判斷位為11,所以不作加減運算,向右移位後的結果為1111 1010,這就是運算結果(—6). 這個乘法的過程描述如下表所示,表中乘積一欄表示的是R0、R1的內容以及一個輔助位P,黑體字表示對兩個判斷位的判斷. 用Booth補碼一位乘法計算2 ×(-3)的過程 迴圈 步驟 乘積（R0,R1, P） 0 初始值 0000 1101 0 第一次迴圈 1c：減0010 1110 1101 0 2：右移1位 1111 0110 1 第二次迴圈 1b：加0010 0001 0110 1 2：右移1位 0000 1011 0 第三次迴圈 1c：減0010 1110 1011 0 2：右移1位 1111 0101 1 第四次迴圈 1a：無操作 1111 0101 1 2：右移1位 1111 1010 1 4．補碼兩位乘 補碼兩位乘運算規則是根據補碼一位乘的規則,把比較yiyi+1的狀態應執行的操作和比較yi-1yi 的狀態應執行的操作合併成一步,便可得出補碼兩位乘的運算方法. 補碼兩位乘法運算規則如下 判斷位yi-1y iyi+1 操作內容 000 [zi+1]補=2-2[zi]補 001 [zi+1]補=2-2{[zi]補+[x]補} 010 [zi+1]補=2-2{[zi]補+[x]補} 011 [zi+1]補=2-2{[zi]補+2[x]補} 100 [zi+1]補=2-2{[zi]補+2[-x]補} 101 [zi+1]補=2-2{[zi]補+ [-x]補} 110 [zi+1]補=2-2{[zi]補+-x}補} 111 [zi+1]補=2-2[zi]補 由上表可見,操作中出現加2[x]補和加2[-x]補,故除右移兩位的操作外,還有被乘數左移一位的操作；而加2[x]補和加2[-x]補,都可能因溢位而侵佔雙符號位,故部分積和被乘數採用三位符號位. 例：[x]補=0.0101,[y]補=1.0101 求： [x? y]補. 求解過程如下表所示.其中乘數取兩位符號位即11.0101,[-x]補=1.1011取三符號位為111.1011. 部分積 乘數 說 明 000.0000 + 000.0101 1101010 判斷位為010,加[x]補 000.0101 000.0001 + 000.0101 0111010 →2位 判斷位為010,加[x]補 000.0110 000.0001 + 111.1011 01 1001110 →2位 判斷位為110,加[-x]補 111.1100 1001 最後一步不移位,得[x? y]補 故[x? y]補=1.11001001 可見,與補碼一位乘相比,補碼兩位乘的部分積多取一位符號位（共3位）,乘數也多取一位符號位（共2位）,這是由於乘數每次右移2位,且用3位判斷,故採用雙符號位更便於硬體實現.可見,當乘數數值位為偶數時,乘數取2位符號位,共需作n/2次移位,最多作n/2+1次加法,最後一步不移位；當n為奇數時,可補0變為偶數位,以簡化邏輯操作.也可對乘數取1位符號位,此時共作n/2+1次加法和n/2+1次移位（最後一步移一位）. 對於整數補碼乘法,其過程與小數乘法完全相同.為了區別於小數乘法,在書寫上可將符號位和數值位中間的“.”改為“,”即可. 再補充一道例子,增加一下理解.呵呵 例1.37 設被乘數M=0111（7）,乘數Q=0011（3）,相乘過程如下：(其中的①②……是我自己加上去的) A Q Q-1 ①0000 0011 0 初始值 ②1001 0011 0 A=A-M ③1100 1001 1 右移（第1次迴圈） ④1110 0100 1 右移（第2次迴圈） ⑤0101 0100 1 A=A+M ⑥0010 1010 0 右移（第3次迴圈） ⑦0001 0101 0 右移（第4次迴圈） 乘法運算結束後,所得結果共8位,A暫存器中是乘積的高位部分,Q暫存器中是乘積的低位部分,即乘積=0010101=(21)(十進位制） 例1.38 設被乘數M=0111(7),乘數Q＝1101（－3）,相乘過程如下： A Q Q－1 0000 1101 0 初始值 1001 1101 0 A＝A－M 1100 1110 1 右移（第1次迴圈） 0011 1110 1 A＝A＋M 0001 1111 0 右移（第2次迴圈） 1010 1111 0 A＝A－M 1101 0111 1 右移（第3次迴圈） 1110 1011 1 右移（第4次迴圈） 乘積=11101011=(-21)(十進位制)
比較好的帶符號數乘法的方法是布斯(Booth)演算法.它採用相加和相減的操作計算補碼資料的乘積.Booth演算法對乘數從低位開始判斷,根據兩個資料位的情況決定進行加法、減法還是僅僅移位操作.判斷的兩個資料位為當前位及其右邊的位(初始時需要增加一個輔助位0),移位操作是向右移動.在上例中,第一次判斷被乘數0110中的最低位0以及右邊的位(輔助位0),得00；所以只進行移位操作；第二次判斷0110中的低兩位,得10,所以作減法操作並移位,這個減法操作相當於減去2a的值；第三次判斷被乘數的中間兩位,得11,於是只作移位操作；第四次判斷0110中的最高兩位,得01,於是作加法操作和移位,這個加法相當於加上8a的值,因為a的值已經左移了三次. 一般而言,設y=y0,yly2…yn為被乘數,x為乘數,yi是a中的第i位(當前位).根據yj與yi+1的值,Booth演算法表示如下表所示,其操作流程如下圖所示.在Booth演算法中,操作的方式取決於表示式(yi+1-yi)的值,這個表示式的值所代表的操作為： 0 無操作 +1 加x -1 減x Booth演算法操作表示 yi yi+1 操作 說明 0 0 無 處於0串中,不需要操作 0 1 加x 1串的結尾 1 0 減x 1串的開始 1 1 無 處於1串中,不需要操作 乘法過程中,被乘數相對於乘積的左移操作可表示為乘以2,每次迴圈中的運算可表示為對於x(yi+1-yi)2^31-i項的加法運算(i=3l,30,…,1,0).這樣,Booth演算法所計算的結果 可表示為： x×(0-y31)×2^0 +x×(y31-y30)×2^1 +x×(y30-y29)×2^2 … [1] +x×(y1-y0)×2^31 =x×(-y0×231 +y1×2^30 +y2×2^29+y31×2^0) =x×y 例：用Booth演算法計算2×(-3). [2]補=0010, [-3]補=1101,在乘法開始之前,R0和R1中的初始值為0000和1101,R2中的值為0010. 在乘法的第一個迴圈中,判斷R1的最低位和輔助位為10,所以進入步驟1c,將R0的值減去R2的值,結果1110送人R0,然後進入第二步,將R0和Rl右移一位,R0和R1的結果為11110110,輔助位為l. 在第二個迴圈中,首先判斷Rl的最低位和輔助位為0l,所以進入步驟1b,作加法,R0+R2=1111+0010,結果0001送入R0,這時R0R1的內容為0001 0110,在第二步右移後變為0000 1011,輔助位為0. 在第三次迴圈中,判斷位為10,進入步驟lc,R0減去R2,結果1110送入R0,R1不變；步驟2移位後R0和R1的內容為1111 01011,輔助位為1. 第四次迴圈時,因兩個判斷位為11,所以不作加減運算,向右移位後的結果為1111 1010,這就是運算結果(—6). 這個乘法的過程描述如下表所示,表中乘積一欄表示的是R0、R1的內容以及一個輔助位P,黑體字表示對兩個判斷位的判斷. 用Booth補碼一位乘法計算2 ×(-3)的過程 迴圈 步驟 乘積（R0,R1, P） 0 初始值 0000 1101 0 第一次迴圈 1c：減0010 1110 1101 0 2：右移1位 1111 0110 1 第二次迴圈 1b：加0010 0001 0110 1 2：右移1位 0000 1011 0 第三次迴圈 1c：減0010 1110 1011 0 2：右移1位 1111 0101 1 第四次迴圈 1a：無操作 1111 0101 1 2：右移1位 1111 1010 1 4．補碼兩位乘 補碼兩位乘運算規則是根據補碼一位乘的規則,把比較yiyi+1的狀態應執行的操作和比較yi-1yi 的狀態應執行的操作合併成一步,便可得出補碼兩位乘的運算方法. 補碼兩位乘法運算規則如下 判斷位yi-1y iyi+1 操作內容 000 [zi+1]補=2-2[zi]補 001 [zi+1]補=2-2{[zi]補+[x]補} 010 [zi+1]補=2-2{[zi]補+[x]補} 011 [zi+1]補=2-2{[zi]補+2[x]補} 100 [zi+1]補=2-2{[zi]補+2[-x]補} 101 [zi+1]補=2-2{[zi]補+ [-x]補} 110 [zi+1]補=2-2{[zi]補+-x}補} 111 [zi+1]補=2-2[zi]補 由上表可見,操作中出現加2[x]補和加2[-x]補,故除右移兩位的操作外,還有被乘數左移一位的操作；而加2[x]補和加2[-x]補,都可能因溢位而侵佔雙符號位,故部分積和被乘數採用三位符號位. 例：[x]補=0.0101,[y]補=1.0101 求： [x? y]補. 求解過程如下表所示.其中乘數取兩位符號位即11.0101,[-x]補=1.1011取三符號位為111.1011. 部分積 乘數 說 明 000.0000 + 000.0101 1101010 判斷位為010,加[x]補 000.0101 000.0001 + 000.0101 0111010 →2位 判斷位為010,加[x]補 000.0110 000.0001 + 111.1011 01 1001110 →2位 判斷位為110,加[-x]補 111.1100 1001 最後一步不移位,得[x? y]補 故[x? y]補=1.11001001 可見,與補碼一位乘相比,補碼兩位乘的部分積多取一位符號位（共3位）,乘數也多取一位符號位（共2位）,這是由於乘數每次右移2位,且用3位判斷,故採用雙符號位更便於硬體實現.可見,當乘數數值位為偶數時,乘數取2位符號位,共需作n/2次移位,最多作n/2+1次加法,最後一步不移位；當n為奇數時,可補0變為偶數位,以簡化邏輯操作.也可對乘數取1位符號位,此時共作n/2+1次加法和n/2+1次移位（最後一步移一位）. 對於整數補碼乘法,其過程與小數乘法完全相同.為了區別於小數乘法,在書寫上可將符號位和數值位中間的“.”改為“,”即可. 再補充一道例子,增加一下理解.呵呵 例1.37 設被乘數M=0111（7）,乘數Q=0011（3）,相乘過程如下：(其中的①②……是我自己加上去的) A Q Q-1 ①0000 0011 0 初始值 ②1001 0011 0 A=A-M ③1100 1001 1 右移（第1次迴圈） ④1110 0100 1 右移（第2次迴圈） ⑤0101 0100 1 A=A+M ⑥0010 1010 0 右移（第3次迴圈） ⑦0001 0101 0 右移（第4次迴圈） 乘法運算結束後,所得結果共8位,A暫存器中是乘積的高位部分,Q暫存器中是乘積的低位部分,即乘積=0010101=(21)(十進位制） 例1.38 設被乘數M=0111(7),乘數Q＝1101（－3）,相乘過程如下： A Q Q－1 0000 1101 0 初始值 1001 1101 0 A＝A－M 1100 1110 1 右移（第1次迴圈） 0011 1110 1 A＝A＋M 0001 1111 0 右移（第2次迴圈） 1010 1111 0 A＝A－M 1101 0111 1 右移（第3次迴圈） 1110 1011 1 右移（第4次迴圈） 乘積=11101011=(-21)(十進位制)