台式演算法

A. 求布斯演算法舉例詳解

布斯乘法演算法（英語：Booth's multiplication algorithm）是計算機中一種利用數的2的補碼形式來計算乘法的演算法。該演算法由安德魯·唐納德·布斯於 1950 年發明，當時他在倫敦大學柏貝克學院做晶體學研究。布斯曾使用過一種台式計算器，由於用這種計算器來做移位計算比加法快，他發明了該演算法來加快計算速度。布斯演算法在計算機體系結構學科中備受關注。
對於 N 位乘數 Y，布斯演算法檢查其2的補碼形式的最後一位和一個隱含的低位，命名為 y-1 ，初始值為 0 。對於 yi, i = 0, 1, ..., N - 1，考察 yi 和 yi - 1 。當這兩位相同時，存放積的累加器 P 的值保持不變。當 yi = 0 且 yi - 1 = 1 時，被乘數乘以 2i 加到 P 中。當 yi = 1 且 yi - 1 = 0 時，從 P 中減去被乘數乘以 2i 的值。演算法結束後， P 中的數即為乘法結果。
該演算法對被乘數和積這兩個數的表達方式並沒有作規定。一般地，和乘數一樣，可以採用2的補碼方式表達。也可以採用其他計數形式，只要支持加減法就行。這個演算法從乘數的最低位執行到最高位，從 i = 0 開始，接下來和 2i 的乘法被累加器 P 的算術右移所取代。較低位可以被移出，加減法可以只在 P 的前 N 位上進行。