布斯乘法算法

✍ dations ◷ 2025-06-09 09:04:41 #电脑架构,计算机科学,算法,二进制算术

布斯乘法算法(英语: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串时),布斯算法较一般的乘法算法执行的加减法运算少。

相关

  • 安乃近安乃近(英文名 Metamizole Sodium;Metamizole、dipyrone、Sulpyrine),,一种解热镇痛药,1920年被德国 Hoechst AG公司合成,1922年开始批量生产。由氨基比林、甲醛和亚硫酸钠缩合得到
  • 比什凯克比什凯克(柯尔克孜语西里尔字母:Бишкек,柯尔克孜语阿拉伯字母:بىشكەك),吉尔吉斯斯坦共和国首都。亦是该国的政治、经济、交通、科教及文化中心。比什凯克是吉尔吉斯斯
  • 施肥堆肥是被分解和回收的有机物质作为肥料和土壤调理剂(英语:Soil conditioner)。堆肥是有机农业的关键成分。在最简单的层面上,堆肥过程需要将一批被称为绿色废物(英语:Green waste)(
  • 下淡水溪铁桥坐标:22°39′41.27″N 120°26′9.72″E / 22.6614639°N 120.4360333°E / 22.6614639; 120.4360333下淡水溪铁桥位于台湾铁路管理局屏东线九曲堂车站至六块厝车站间,桥面横
  • 酸沼木乃伊酸沼木乃伊(Bog body),又称沼泽木乃伊、沼泽人、湿地遗体,是指在酸沼中自然木乃伊化的人类尸体。目前被发现的数具酸沼木乃伊来自全球各地,年代从公元前8000年至第二次世界大战期
  • 西拉西拉葡萄(英语:Shiraz、Syrah)简称希拉,也叫做西拉子、设拉子。是一个被广泛种植的酿酒葡萄品种,欧亚种,其广泛程度可能只有梅洛葡萄和赤霞珠能与其相比。其酿造的葡萄酒,风味与香
  • 哈德逊-博根轻轨铁路哈德逊-卑尔根轻轨(英语:Hudson–Bergen Light Rail,简称HBLR)是一个位于美国新泽西州哈德逊郡的轻轨铁路系统;为新泽西运输公司所拥有,由二十一世纪铁路公司运营;自2000年4月通车
  • 盔蟹总科见内文盔蟹科(Corystidae)是短尾下目(螃蟹)以下的一个科,原属黄道蟹总科,现时独立出来成为盔蟹总科(Corystoidea)。它包含有最古老的蟹派化石品种Hebertides jurassica,可追溯远至侏
  • 乔治·霍林伯瑞乔治·霍林伯瑞(George Hollingbery,1963年10月12日-)是一位英格兰政治人物 ,他的党籍是保守党。自2010年开始,他担任米恩河谷选区选出的英国下议院议员。他拥有宾夕法尼亚大学的M
  • 石川康长石川康长(1554年-1643年1月30日),是安土桃山时代至江户时代前期的武将和大名。父亲是石川数正。信浓松本藩第2代藩主。在天文23年(1554年)出生,家中长男。在天正13年(1585年)与父亲一