勵志

勵志人生知識庫

布斯乘法

布斯乘法是一種利用數的2的補碼形式來計算乘法的算法,由安德魯·唐納德·布斯於1950年發明。該算法在計算機體系結構學科中備受關注,主要用於加快乘法運算的速度。

布斯乘法的算法過程如下:

對於N位乘數Y,檢查其2的補碼形式的最後一位和一個隱含的低位,命名為y[i-1],初始值為0。對於y[i],i=0,1,...,N-1,考察y[i]和y[i-1]。

當這兩位相同時,存放積的累加器P的值保持不變。當y[i]=0且y[i-1]=1時,被乘數乘以2^i加到P中。當y[i]=1且y[i-1]=0時,從P中減去被乘數乘以2^i的值。

算法結束後,P中的數即為乘法結果。該算法對被乘數和積這兩個數的表達方式並沒有作規定,一般地,和乘數一樣,可以採用2的補碼方式表達,也可以採用其他計數形式,只要支持加減法就行。

布斯乘法實現過程如下:

確定A和S的值,以及P的初始值。這三個數字的總長度應等於(x+y+1)。對於A,以m的補碼值填充前x位(最靠左的位),用零填滿剩下的(y+1)位;對於S,以(-m)的補碼值填充前x位,用零填滿剩下的(y+1)位;對於P,用0填滿最左的x位,將r的值附加在尾部;最右一位用零占位(輔助位,當i=0時i-1=-1,指的就是這個輔助位)。

乘數最低位增加一位輔助位。若輔助位為0且乘數當前位為1,則加法操作;若輔助位為1且乘數當前位為0,則減法操作;若輔助位和乘數當前位一正一負,則不做任何操作。然後算術右移一位,得到部分積。重複以上步驟,最終得到乘法結果。