问答文章1 问答文章501 问答文章1001 问答文章1501 问答文章2001 问答文章2501 问答文章3001 问答文章3501 问答文章4001 问答文章4501 问答文章5001 问答文章5501 问答文章6001 问答文章6501 问答文章7001 问答文章7501 问答文章8001 问答文章8501 问答文章9001 问答文章9501

计算机中乘法算法如何设计?

发布网友 发布时间:2022-07-20 05:37

我来回答

1个回答

热心网友 时间:2023-11-10 22:08

1、无符号乘法。

无符号的乘法与加法类似,它的运算方式是比较简单的,只是也可能产生溢出。对于两个w位的无符号数来说,它们的乘积范围在0到(2w-1)2之间,因此可能需要2w位二进制才能表示。

因此由于位数的*,假设两个w位的无符号数的真实乘积为pro,根据截断的规则,则实际得到的乘积为 pro mod 2w。

2、补码乘法。

与加法运算类似,补码乘法也是建立在无符号的基础之上的,因此我们可以很容易的得到,对于两个w位的补码数来说,假设它们的真实乘积为pro,

则实际得到的乘积为:

U2Tw(pro mod 2w。

上面的式子有一个假设,就是假设对于w位的两个补码数来说,它们的乘积的低w位与无符号数乘积的低w位是一样的。这意味着计算机可以使用一个指令执行无符号和补码的乘法运算。

3、乘法运算的优化。

根据小学所学的乘法运算,假设两个w位的二进制数相乘,则需要进行w次与运算,然后进行w - 1次加法运算才能得到结果。

从此不难看出,乘法运算的时间周期是很长的。因此计算机界的高手们想出了一种方式可以优化乘法运算的效率,就是使用移位和加法来替代乘法。

上述优化的前提是对于一个w位的二进制数来说,它与2k的乘积,等同于这个二进制数左移k位,在低位补k个0。在书中对这一等式进行了证明,过程如下。

这个过程主要应用了无符号编码的公式。

有了上面的基础,就可以使用移位和加法对乘法优化了。

对于任意一个整数y,它总能使用二进制序列表示(假设不超过二进制的表示范围),因此可以将x和y乘积的二进制序列表示为如下形式(此公式在书中没有展现)。

x * y = x * (yw-12w-1 + ... + y020) =  (x << w-1) * yw-1 +....+ (x << 0 ) * y0。

举个例子,对于x * 17,可以计算x * 16 + x = (x << 4) + x ,这样算下来的话,只需要一次移位一次加法就可以搞定这个乘法运算。

而对于x * 14,则可以计算 x * 8 + x * 4 + x * 2 = (x << 3) + (x << 2) + (x << 1) ,更快的方式可以这么计算,x * 16 - x * 2 = (x << 4) - (x << 1) 。

这里最后需要提一下的是,加法、减法和移位的速度并不会总快于乘法运算,因此是否要进行上面的优化就取决于二者的速度了。

4、二进制乘法的运算步骤。

二进制数乘法过程可仿照十进制数乘法进行。

但由于二进制数只有0或1两种可能的乘数位,导致二进制乘法更为简单。二进制数乘法的法则为:

1、0×0=0。

2、0×1=1×0=0。

3、1×1=1。

例如:1001和1010相乘的过程如下:

由低位到高位,用乘数的每一位去乘被乘数,若乘数的某一位为1,则该次部分积为被乘数;若乘数的某一位为0,则该次部分积为0。

某次部分积的最低位必须和本位乘数对齐,所有部分积相加的结果则为相乘得到的乘积。

参考资料来源:百度百科——二进制乘法

声明声明:本网页内容为用户发布,旨在传播知识,不代表本网认同其观点,若有侵权等问题请及时与本网联系,我们将在第一时间删除处理。E-MAIL:11247931@qq.com
...啊?我从嘴里吐出去是直的算过肺了吗?我不会从鼻子里出去_百度... 恶心呕吐是什么? 高考数学大题应注意哪些问题呢? 高考数学可不可以用高等数学啊 高考数学 基础知识点 常见考查方式 高考数学考什么内容 一般纳税人如何交所得税 以前的QQ忘记密码了那时候不要了就不找回密码了,现在想找回来,但是又没... 常州机场坐飞机流程 常州机场大巴时刻表 ...我早上九点起飞的飞机, 然后我这的机场快线大巴到机场时70分钟,_百 ... 儿童适合用擦脸油吗?还是什么都不抹? 有哪些女童冬天用的擦脸油,不油腻不显黑? 快手到一万粉丝咋一分钱没有? 防疫警示语 qq登录锁 手机绑定的 怎么解除 北京金硕果知识产权代理事务所(普通合伙)怎么样? 北京金知睿知识产权代理事务所(普通合伙)怎么样? 奥拉星怎么脱装备 奥拉星神兵之令有什么用 奥拉星怎么换装备 奥拉星守护月光镇(【无尽神兵】银)攻略 奥拉星神兵升级如何满级 奥拉星神兵封印卡怎么获得 奥拉星装备怎么用 奥拉星无尽神兵怎么用 奥拉星至高冠冕之谕真理之后装什么神兵 求question和problem的区别 在两年前他从不做运动不喜欢学习英语 十不准指的是什么 十不准,十不交接,十不执行是什么意思 如何正确护肤,看你的步骤对了吗 冬天正确护肤的步骤是怎么样的? 微店上买的课,看了一点感觉没有用,不想学了,商家不退款怎么办? 请问青岛哪个地方有摆文玩核桃摊位比较便宜的 青岛在职人员可以开微店? 丽颜肌秋冬护肤正确步骤应该这么做? 创维盒子恢复出厂设置该如何进入recovery? 冬天晚上护肤步骤是怎么样的? 小说《时间条约》在哪可以看? 手机指南针为什么反了? 高级的id有哪些? 现在的股票行情是要清仓还是加仓? 蕃茄炒薯条的做法,蕃茄炒薯条怎么做好吃,蕃茄 芹菜炒薯条的做法,芹菜炒薯条怎么做好吃,芹菜 手艺还是太差,本来想炒土豆丝的结果刀工太差直接变成炒薯条了, 快手上给别人涨热度是真的吗? 西安医保电话人工服务咨询电话 阎良区医疗保险事业管理处 碑林区医疗保险中心在哪 西安市医保经办中心