布斯乘法算法

布斯乘法算法（英語：Booth's multiplication algorithm）是計算機中一種利用數的2的補碼形式來計算乘法的算法。該算法由安德魯·唐納德·布思於1950年發明，當時他在倫敦大學柏貝克學院做晶體學研究。布斯曾使用過一種台式計算器，由於用這種計算器來做移位計算比加法快，他發明了該算法來加快計算速度。布斯算法在計算機體系結構學科中備受關注。

算法描述

對於N位乘數Y，布斯算法檢查其2的補碼形式的最後一位和一個隱含的低位，命名為y_-1，初始值為0。對於y_i, i = 0, 1, ..., N - 1，考察y_i和y_{i - 1}。當這兩位相同時，存放積的累加器P的值保持不變。當y_i = 0且y_{i - 1} = 1時，被乘數乘以2ⁱ加到P中。當y_i = 1且y_{i - 1} = 0時，從P中減去被乘數乘以2ⁱ的值。算法結束後，P中的數即為乘法結果。

該算法對被乘數和積這兩個數的表達方式並沒有作規定。一般地，和乘數一樣，可以採用2的補碼方式表達。也可以採用其他計數形式，只要支持加減法就行。這個算法從乘數的最低位執行到最高位，從i = 0開始，接下來和2_i的乘法被累加器P的算術右移所取代。較低位可以被移出，加減法可以只在P的前N位上進行。^[1]

典型實現

布斯算法的實現，可以通過重複地在P上加兩個預設值A和 S 其中的一個，然後對P實施算術右移。設m和r分別為被乘數和乘數，再令x和y分別為m和r中的數字位數。

1. 確定A和S的值，以及P的初始值。這三個數字的長度都應等於（x + y + 1）：
   1. 對於A，以m的值填充前x位（最靠左的位），用零填滿剩下的（y + 1）位；
   2. 對於S，以（ - m）的值填充前x位，用零填滿剩下的（y + 1）位；
   3. 對於P：用0填滿最左的x位，將r的值附加在尾部；最右一位用零占位（輔助位，當i=0時i-1=-1,指的就是這個輔助位）；
2. 考察P的最右兩位：
   1. 如果等於01，求出P + A的值，忽略上溢；
   2. 如果等於10，求出P + S的值，忽略上溢；
   3. 如果等於00，不做任何運算，在下一步中直接採用P的值；
   4. 如果等於11，不做任何運算，在下一步中直接採用P的值。
3. 對第2步中得到的值進行算術右移一位，並將結果賦給P；
4. 重複第2步和第3步，一共做y次；
5. 舍掉P的最右一位，得到的即為m和r的積。

換另一種說法：把前x位用一個單獨的數R0表示，中間y位用另一個數表示R1表示，輔助位用Z表示 在這裡，要通過重複的把R0加上或者減去m來得到結果。具體如下： 初始值R0=0,R1=r.Z=0,此時來考查yi和yi-1這兩位，在這裡就是r的最後一位和Z的值。這裡要說下為什麼每次看的都是這兩位了。在下邊每次運算後都會把R0,R1,Z中的值右移一次，RO的最後一位移入R1的高位，R1的最後一位移入Z。這裡要注意的是在右移R0時，如果他的最高位是1,則移位後最高位用1填充，如果最高位是0，移位後最高位用0填充。接下來要按r的最後一位和Z的值來判斷怎麼加減了：

1. 1. 如果為01,則R0+m，進位忽略。然後R0,R1,Z右移一位，再下一步判斷，直到把R1的每一位都判斷過後為結束
   2. 如果為10,則R0-m，借位忽略（只要x位的R0的值）。然後R0,R1,Z右移一位，再下一步判斷，直到把R1的每一位都判斷過後為結束
   3. 如果為00或是11,則R0的值保持不變。然後R0,R1,Z右移一位，再下一步判斷，直到把R1的每一位都判斷過後為結束

最後是結果，結果就是R0並上R1的值。比如R0=3,R1=25,結果就是325.

算法原理

考慮一個由若干個0包圍著若干個1的正的二進制乘數，比如00111110，積可以表達為：

${\displaystyle M\times \,^{\prime \prime }0\;0\;1\;1\;1\;1\;1\;0\,^{\prime \prime }=M\times (2^{5}+2^{4}+2^{3}+2^{2}+2^{1})=M\times 62}$

其中，M代表被乘數。變形為下式可以使運算次數可以減為兩次：

${\displaystyle M\times \,^{\prime \prime }0\;1\;0\;0\;0\;0{\mbox{-1}}\;0\,^{\prime \prime }=M\times (2^{6}-2^{1})=M\times 62}$。

事實上，任何二進制數中連續的1可以被分解為兩個二進制數之差：

${\displaystyle (\ldots 0\overbrace {1\ldots 1} ^{n}0\ldots )_{2}\equiv (\ldots 1\overbrace {0\ldots 0} ^{n}0\ldots )_{2}-(\ldots 0\overbrace {0\ldots 1} ^{n}0\ldots )_{2}}$。

因此，我們可以用更簡單的運算來替換原數中連續為1的數字的乘法，通過加上乘數，對部分積進行移位運算，最後再將之從乘數中減去。它利用了我們在針對為零的位做乘法時，不需要做其他運算，只需移位這一特點，這很像我們在做和99的乘法時利用99 = 100 − 1這一性質。這種模式可以擴展應用於任何一串數字中連續為1的部分（包括只有一個1的情況）。那麼，

${\displaystyle M\times \,^{\prime \prime }0\;0\;1\;1\;1\;0\;1\;0\,^{\prime \prime }=M\times (2^{5}+2^{4}+2^{3}+2^{1})=M\times 58}$

${\displaystyle M\times \,^{\prime \prime }0\;1\;0\;0{\mbox{-1}}\;0\;1\;0\,^{\prime \prime }=M\times (2^{6}-2^{3}+2^{1})=M\times 58}$。

布斯算法遵從這種模式，它在遇到一串數字中的第一組從0到1的變化時（即遇到01時）執行加法，在遇到這一串連續1的尾部時（即遇到10時）執行減法。這在乘數為負時同樣有效。當乘數中的連續1比較多時（形成比較長的1串時），布斯算法較一般的乘法算法執行的加減法運算少。

參考來源

1. Chi-hau Chen. Signal processing handbook. CRC Press. 1988: 234. ISBN 9780824779566.

延伸閱讀

1. Andrew D. Booth. A signed binary multiplication technique. The Quarterly Journal of Mechanics and Applied Mathematics, Volume IV, Pt. 2 [1] （頁面存檔備份，存於網際網路檔案館）
2. Collin, Andrew. Andrew Booth's Computers at Birkbeck College （頁面存檔備份，存於網際網路檔案館）. Resurrection, Issue 5, Spring 1993. London: Computer Conservation Society.
3. Patterson, David and John Hennessy. Computer Organization and Design: The Hardware/Software Interface, Second Edition. ISBN 1-55860-428-6. San Francisco, California: Morgan Kaufmann Publishers. 1998.
4. Stallings, William. Computer Organization and Architecture: Designing for performance, Fifth Edition. ISBN 0-13-081294-3. New Jersey: Prentice-Hall, Inc.. 2000.

外部連結

• Radix-4 Booth Encoding （頁面存檔備份，存於網際網路檔案館）
• Radix-8 Booth Encoding in A Formal Theory of RTL and Computer Arithmetic
• Booth's Algorithm
• Booth's Algorithm JavaScript Simulator （頁面存檔備份，存於網際網路檔案館）
• Implementation in Verilog