如何检测溢出,同时乘积两个2的补整数?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (13)

我想乘两个数字,并检测是否有溢出。最简单的方法是什么?

提问于
用户回答回答于

检查一个是否小于最大值除以另一个

2的补码与它几乎没有任何关系,因为如果x *(2 n - x)> 2 M等于(x * 2 n - x 2)> 2 M,或者x 2 <(x * 2 n - 2 M),因此无论如何您必须比较溢出数字(x 2可能会溢出,而结果可能不会)。

用户回答回答于

将两个32位数相乘,得到一个64位的答案,两个8s得到一个16,等等,二进制乘法只是简单地移动和加法。

二进制使得乘法比十进制简单,例如,以二进制数为例。

0b100 *
0b100 

就像学校里的十进制数学一样,你可以从下操作数中最不重要的位开始,然后根据上操作数中的所有位置将它相乘,除了二进制,只有两个选项可以被乘以零--这意味着你不必加到结果中,或者乘以一个,这意味着你只需要移动和加法,就不需要像小数点那样实际的乘法了。

  000 : 0 * 100
 000  : 0 * 100
100   : 1 * 100

把这些列加起来,答案是0b10000

在最坏的情况下---*0b111

0b00111 +
0b01110 +
0b11100 

这会导致加法中的进位,从而产生0b110001。6位。3位操作数乘以3位操作数3+3=6位最坏情况。

-8 * 7 = -56
0b1000 * 0b0111 = 0b1001000 
-1 * 7 = -7 = 0b1001
-8 * -8 = 64 = 0b01000000
-1 * -1 = 2 = 0b010
-1 * -8 = 8 = 0b01000
7 * 7 = 49 = 0b0110001

让我们把正数算为最重要的1加1,负的是最重要的0加1。

-8 * 7 is 4+4=8 bits   actual 7
-1 * 7 is 1+4=5 bits, actual 4 bits
-8 * -8 is 4+4=8 bits, actual 8 bits
-1 * -1 is 1+1=2 bits, actual 3 bits
-1 * -8 is 1+4=5 bits, actual 5 bits
7 * 7 is 4+4=8 bits, actual 7 bits.

所以这个规则起作用了,除了-1*-1,你可以看到,我调用了一个负1位,因为加1的东西是零加1。

扫码关注云+社区