[科普中國]-布斯乘法算法

布斯乘法算法是計算機(jī)中一種利用數(shù)的2的補碼形式來計算乘法的算法。該算法由安德魯·唐納德·布斯于1950 年發(fā)明，當(dāng)時他在倫敦大學(xué)伯克貝克學(xué)院做晶體學(xué)研究。布斯曾使用過臺式計算器，由于用這種計算器來做移位計算比加法快，他發(fā)明了該算法來加快計算速度。布斯算法在計算機(jī)體系結(jié)構(gòu)學(xué)科中備受關(guān)注。

算法描述對于 N 位乘數(shù) Y，布斯算法檢查其2的補碼形式的最后一位和一個隱含的低位，命名為 y[i-1] ，初始值為 0 。對于 y[i], i = 0, 1, ..., N - 1，考察 y[i] 和 y[i - 1 ]。當(dāng)這兩位相同時，存放積的累加器 P 的值保持不變。當(dāng) y[i] = 0 且 y[i - 1] = 1 時，被乘數(shù)乘以 2^i 加到 P 中。當(dāng) y[i]= 1 且 y[i - 1] = 0 時，從 P 中減去被乘數(shù)乘以 2^i 的值。算法結(jié)束后， P 中的數(shù)即為乘法結(jié)果。

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

典型實現(xiàn)布斯算法的實現(xiàn)，可以通過重復(fù)地在 P 上加兩個預(yù)設(shè)值 A 和 S 其中的一個，然后對 P 實施算術(shù)右移。設(shè) m 和 r 分別為被乘數(shù)和乘數(shù)，再令 x 和 y 分別為 m 和 r 中的數(shù)字位數(shù)。

確定 A 和 S 的值，以及 P 的初始值。這三個數(shù)字的總長度應(yīng)等于( x + y + 1 )：

對于 A ，以 m 的補碼值填充前x位（最靠左的位），用零填滿剩下的( y + 1 )位；

對于 S ，以( - m )的補碼值填充前x位，用零填滿剩下的( y + 1 )位；

對于 P ：用0填滿最左的 x 位，將 r 的值附加在尾部；最右一位用零占位（輔助位，當(dāng)i=0時i-1=-1,指的就是這個輔助位）；

考察 P 的最右兩位：

如果等于 01，求出 P + A 的值，忽略上溢；

如果等于 10，求出 P + S 的值，忽略上溢；

如果等于 00，不做任何運算，在下一步中直接采用 P 的值；

如果等于 11，不做任何運算，在下一步中直接采用 P 的值。

對第 2 步中得到的值進(jìn)行算術(shù)右移一位，并將結(jié)果賦給 P ；

重復(fù)第 2 步和第 3 步，一共做 y 次；

舍掉 P 的最右一位，得到的即為 m 和 r 的積。

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

如果為01,則R0+m，進(jìn)位忽略。然后R0,R1,Z右移一位，再下一步判斷，直到把R1的每一位都判斷過后為結(jié)束

如果為10,則R0-m，借位忽略（只要x位的R0的值）。然后R0,R1,Z右移一位，再下一步判斷，直到把R1的每一位都判斷過后為結(jié)束

如果為00或是11,則R0的值保持不變。然后R0,R1,Z右移一位，再下一步判斷，直到把R1的每一位都判斷過后為結(jié)束

最后是結(jié)果，結(jié)果就是R0并上R1的值。比如R0=3,R1=25,結(jié)果就是325.

注意：在實際應(yīng)用中，“減去m”多用“加上-m”來代替。2

算法原理考慮一個由若干個0包圍著若干個1的正的二進(jìn)制乘數(shù)，比如00111110，積可以表達(dá)為：

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

事實上，任何二進(jìn)制數(shù)中連續(xù)的1可以被分解為兩個二進(jìn)制數(shù)之差：

因此，我們可以用更簡單的運算來替換原數(shù)中連續(xù)為1的數(shù)字的乘法，通過加上乘數(shù)，對部分積進(jìn)行移位運算，最后再將之從乘數(shù)中減去。它利用了我們在針對為零的位做乘法時，不需要做其他運算，只需移位這一特點，這很像我們在做和99的乘法時利用99=100?1這一性質(zhì)。這種模式可以擴(kuò)展應(yīng)用于任何一串?dāng)?shù)字中連續(xù)為1的部分（包括只有一個1的情況）。那么，

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

本詞條內(nèi)容貢獻(xiàn)者為:

楊明 - 副教授 - 西南大學(xué)