布斯乘法算法(Booth's multiplication algorithm)是一種用於計算機中快速計算乘法的算法。它利用了數的2的補碼形式,由安德魯·唐納德·布斯於1950年發明。該算法的基本思想是通過檢查乘數的2的補碼形式的最後一位和一個隱含的低位(初始值為0),來確定在乘法計算中應該進行的操作。具體步驟如下:
對於乘數Y的每一位y[i],其中i從0到N-1(N是乘數的位數),考察y[i]和y[i-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中的數即為乘法結果。
布斯算法的實現可以通過在P上重複加減預設值A和S,然後對P實施算術右移來實現。A和S的值以及P的初始值需要根據被乘數和乘數的位數來確定。A是以被乘數的補碼值填充的前x位(最靠左的位),用零填滿剩下的(y+1)位;S是以(-m)的補碼值填充的前x位,用零填滿剩下的(y+1)位;P則用0填滿最左的x位,將乘數的值附加在尾部,最右一位用零占位。
通過這種方式,布斯乘法算法能夠在計算機體系結構中高效地執行乘法運算,減少計算時間和資源消耗。