布斯乘法算法

✍ dations ◷ 2025-04-03 10:38:05 #电脑架构,计算机科学,算法,二进制算术

布斯乘法算法(英语:Booth's multiplication algorithm)是计算机中一种利用数的2的补码形式来计算乘法的算法。该算法由安德鲁·唐纳德·布思于1950年发明,当时他在伦敦大学柏贝克学院做晶体学研究。布斯曾使用过一种台式计算器,由于用这种计算器来做移位计算比加法快,他发明了该算法来加快计算速度。布斯算法在计算机体系结构学科中备受关注。

对于位乘数,布斯算法检查其2的补码形式的最后一位和一个隐含的低位,命名为-1,初始值为0。对于, = 0, 1, ..., - 1,考察 - 1。当这两位相同时,存放积的累加器的值保持不变。当 = 0且 - 1 = 1时,被乘数乘以2加到中。当 = 1且 - 1 = 0时,从中减去被乘数乘以2的值。算法结束后,中的数即为乘法结果。

该算法对被乘数和积这两个数的表达方式并没有作规定。一般地,和乘数一样,可以采用2的补码方式表达。也可以采用其他计数形式,只要支持加减法就行。这个算法从乘数的最低位执行到最高位,从 = 0开始,接下来和2的乘法被累加器的算术右移所取代。较低位可以被移出,加减法可以只在的前位上进行。

布斯算法的实现,可以通过重复地在上加两个预设值和 S其中的一个,然后对实施算术右移。设和分别为被乘数和乘数,再令和分别为和中的数字位数。

换另一种说法:把前x位用一个单独的数R0表示,中间y位用另一个数表示R1表示,辅助位用Z表示在这里,要通过重复的把R0加上或者减去m来得到结果。具体如下:初始值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的值来判断怎么加减了:

最后是结果,结果就是R0并上R1的值。比如R0=3,R1=25,结果就是325.

考虑一个由若干个0包围着若干个1的正的二进制乘数,比如00111110,积可以表达为:

其中,M代表被乘数。变形为下式可以使运算次数可以减为两次:

事实上,任何二进制数中连续的1可以被分解为两个二进制数之差:

因此,我们可以用更简单的运算来替换原数中连续为1的数字的乘法,通过加上乘数,对部分积进行移位运算,最后再将之从乘数中减去。它利用了我们在针对为零的位做乘法时,不需要做其他运算,只需移位这一特点,这很像我们在做和99的乘法时利用99 = 100 − 1这一性质。这种模式可以扩展应用于任何一串数字中连续为1的部分(包括只有一个1的情况)。那么,

布斯算法遵从这种模式,它在遇到一串数字中的第一组从0到1的变化时(即遇到01时)执行加法,在遇到这一串连续1的尾部时(即遇到10时)执行减法。这在乘数为负时同样有效。当乘数中的连续1比较多时(形成比较长的1串时),布斯算法较一般的乘法算法执行的加减法运算少。

相关

  • 第三代头孢菌素(法语:Cephalosporine、英语:Cephalosporin),又名先锋霉素,是一系列属于β内酰胺类的抗生素。与头霉素一并细分为头孢烯。头孢菌素化合物最初是于1948年,由意大利科学家Giu
  • 抗抑郁药抗抑郁药(英语:Anti-depressant),是一类治疗重度抑郁症(MDD)或其它问题如心境恶劣障碍、焦虑症、强迫症、进食障碍、慢性疼痛、神经性疼痛(英语:Neuropathic pain)的药物,在某些情况下
  • 比鲁尼阿布·拉伊汗·穆罕默德·本·艾哈迈德·比鲁尼(波斯语:ابوریحان محمد بن احمد بیرونی‎,973年-1048年), 波斯学者,生于花剌子模(今中亚乌兹别克斯坦),卒
  • 脑膜炎奈瑟菌脑膜炎双球菌(学名Neisseria meningitidis),又名脑膜炎奈瑟菌或脑脊髓膜炎双球菌,简称为脑膜炎球菌,是一种革兰氏阴性菌,因其所导致的脑膜炎而闻名,亦会造成脑膜炎球菌血症(一种致
  • 单位换算单位换算是指通过乘以换算系数实现不同计量单位间的等量换算。单位换算过程与用户具体情况和预期目的相关。可能受法令、合同、技术规格或其它出版物技术标准的限制。工程判
  • 萜类萜烯(英语:terpene,简称萜,旧称䓝,词由松节油“turpentine”而来)是一系列萜类化合物的总称,属脂类,不溶于水,是分子式为异戊二烯(C5H8)的整数倍的烯烃类化合物。萜烯是一个庞大而多样
  • 海军教育训练暨准则发展指挥部海军教育训练暨准则发展指挥部,简称海军教准部,为中华民国海军最高教育训练机关,为国防部海军司令部下辖机关,成立于1948年(民国37年)。使命为落实“训练基础、精练组合、验证联合
  • 比尤特比尤特县(Butte County, California)是美国加利福尼亚州中央谷地的一个县。面积4,344平方公里,根据美国2000年人口普查数字,共有人口203,171人。县治奥罗维尔 (Oroville)。成立
  • 东河 (佛罗里达州)东河(英语:East River)是一条长约10-英里(16-千米)的河流,位于美国佛罗里达州沃库拉县,在圣马克国家自然保护区汇入圣马克河,最终流入墨西哥湾。
  • 1913年奥斯曼帝国政变1913年奥斯曼帝国政变,又称突袭高门或突袭最高朴特(土耳其语:Bâb-ı Âli Baskını),是发生于1913年1月23日的一场政变,由联合进步委员会发动,领导者是恩维尔帕夏和塔拉特帕夏。