您好,今天芳芳来为大家解答以上的问题。二进制乘法移位如何计算,二进制乘法相信很多小伙伴还不知道,现在让我们一起来看看吧!
1、无符号乘法。
2、无符号的乘法与加法类似,它的运算方式是比较简单的,只是也可能产生溢出。
3、对于两个w位的无符号数来说,它们的乘积范围在0到(2w-1)2之间,因此可能需要2w位二进制才能表示。
4、因此由于位数的限制,假设两个w位的无符号数的真实乘积为pro,根据截断的规则,则实际得到的乘积为 pro mod 2w。
5、2、补码乘法。
6、与加法运算类似,补码乘法也是建立在无符号的基础之上的,因此我们可以很容易的得到,对于两个w位的补码数来说,假设它们的真实乘积为pro,则实际得到的乘积为:U2Tw(pro mod 2w。
7、上面的式子有一个假设,就是假设对于w位的两个补码数来说,它们的乘积的低w位与无符号数乘积的低w位是一样的。
8、这意味着计算机可以使用一个指令执行无符号和补码的乘法运算。
9、3、乘法运算的优化。
10、根据小学所学的乘法运算,假设两个w位的二进制数相乘,则需要进行w次与运算,然后进行w - 1次加法运算才能得到结果。
11、从此不难看出,乘法运算的时间周期是很长的。
12、因此计算机界的高手们想出了一种方式可以优化乘法运算的效率,就是使用移位和加法来替代乘法。
13、上述优化的前提是对于一个w位的二进制数来说,它与2k的乘积,等同于这个二进制数左移k位,在低位补k个0。
14、在书中对这一等式进行了证明,过程如下。
15、这个过程主要应用了无符号编码的公式。
16、有了上面的基础,就可以使用移位和加法对乘法优化了。
17、对于任意一个整数y,它总能使用二进制序列表示(假设不超过二进制的表示范围),因此可以将x和y乘积的二进制序列表示为如下形式(此公式在书中没有展现)。
18、x * y = x * (yw-12w-1 + ... + y020) = (x << w-1) * yw-1 +....+ (x << 0 ) * y0。
19、举个例子,对于x * 17,可以计算x * 16 + x = (x << 4) + x ,这样算下来的话,只需要一次移位一次加法就可以搞定这个乘法运算。
20、而对于x * 14,则可以计算 x * 8 + x * 4 + x * 2 = (x << 3) + (x << 2) + (x << 1) ,更快的方式可以这么计算,x * 16 - x * 2 = (x << 4) - (x << 1) 。
21、这里最后需要提一下的是,加法、减法和移位的速度并不会总快于乘法运算,因此是否要进行上面的优化就取决于二者的速度了。
22、4、二进制乘法的运算步骤。
23、二进制数乘法过程可仿照十进制数乘法进行。
24、但由于二进制数只有0或1两种可能的乘数位,导致二进制乘法更为简单。
25、二进制数乘法的法则为:0×0=0。
26、2、0×1=1×0=0。
27、3、1×1=1。
28、例如:1001和1010相乘的过程如下:由低位到高位,用乘数的每一位去乘被乘数,若乘数的某一位为1,则该次部分积为被乘数;若乘数的某一位为0,则该次部分积为0。
29、某次部分积的最低位必须和本位乘数对齐,所有部分积相加的结果则为相乘得到的乘积。
30、参考资料来源:百度百科——二进制乘法。
本文就为大家分享到这里,希望小伙伴们会喜欢。
标签: