如何在乘以两个2的补码整数时检测溢出？

Question

我想将两个数相乘,并检测是否有溢出.最简单的方法是什么？

Answer 1

将两个32位数相乘得到64位答案,两个8位给出16等,二进制乘法只是移位和加法.因此,如果您说操作数A中有两个32位操作数和第17位,并且操作数b中设置了15或16以上的任何位,则会溢出32位结果.位17向左移位16位33加到32位.

所以问题又是你输入的大小和结果的大小,如果结果大小相同,那么你必须找到两个操作数中最重要的1个,如果结果大于你的结果,则添加这些位位置空间你会溢出.

编辑

如果add中有进位,则将两个3位数相乘将产生5位数或6位数.同样,2位和5位可以产生6或7位等.如果这个问题的原因是问题是看你的结果变量中是否有空间来得到答案,那么这个解决方案将起作用并且对大多数人而言相对较快大多数处理器上的语言 它可以在某些情况下显着更快,在其他情况下显着更慢.它通常很快(取决于它当然是如何实现的)来查看操作数中的位数.如果你可以在你的语言或处理器内完成,那么加倍最大操作数的大小是一个安全的选择.除法是非常昂贵的(慢),并且大多数处理器在操作数大小的任意加倍时都不会少得多.最快的当然是下降到汇编器进行乘法运算并查看溢出位(或将其中一个结果寄存器与零进行比较).如果您的处理器无法在硬件中进行乘法运算,那么无论您做什么,它都会变慢.我猜测asm不是这篇文章的正确答案,尽管它是迄今为止最快且具有最准确的溢出状态.

二进制使乘法与十进制相比变得微不足道,例如取二进制数

0b100 *
0b100 

就像学校中的十进制数学一样,你(可以)从较低操作数上的最低有效位开始,并将它与上部操作数中的所有位置相乘,除了二进制之外,只有两个选项乘以零意味着你不必添加对于结果,或者你乘以一个意味着你只需要移动和添加,就不需要像十进制一样实际乘法.

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

添加列,答案是0b10000

与十进制数学相同,数百列中的1表示复制顶部数字并添加两个零,它在任何其他基础中的工作方式也相同.所以0b100次0b110是0b1000,第二列中的一个就这样复制并在第三列中添加一个零+ 0b10000一个所以复制并添加两个零= 0b11000.

这导致查看两个数字中最重要的位.0b1xx*0b1xx保证将1xxxx添加到答案中,这是添加中的最大位位置,最终添加的其他单个输入没有填充该列或填充更重要的列.从那里你只需要更多的位,以防其他位被添加导致进位.

最糟糕的情况发生在所有的情况下,0b111*0b111

 
0b00111 +
0b01110 +
0b11100 

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

因此,使用最高有效位(不是保存值的寄存器的大小)的操作数大小决定了最坏情况的存储要求.

好吧,假设积极的操作数就是如此.如果你认为其中一些数字是负面的,它会改变一些事情但不会改变.

减4次5,0b1111 ... 111100*0b0000 .... 000101 = -20或0b1111..11101100

它需要4位代表负4和4位来表示正5(不要忘记你的符号位).如果剥离所有符号位,我们的结果需要6位.

让我们看一下4位角的情况

-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之外,你可以看到我调了一个减一位,因为加一个东西找零加一.无论如何,我认为如果这是一个定义的4位*4位机器,你至少会得到4位结果,我将这个问题解释为我需要多于4位来安全地存储答案.因此,这条规则用于回答2s补码数学的问题.

如果你的问题是要准确地确定溢出然后速度是次要的,那么,对于某些系统而言,对于你所做的每一次乘法来说,它真的会非常慢.如果这是你要问的问题,为了获得一些速度,你需要为语言和/或处理器调整一点.如果可以,将最大的操作数加倍,并检查结果大小以上的非零位,或使用除法和比较.如果你不能将操作数大小加倍,则除以并进行比较.除法前检查零.

实际上你的问题并没有说明你所谈论的溢出大小.好老8086 16位16位给出32位结果(硬件),它永远不会溢出.那些具有乘法,32位32位,32位结果,容易溢出的ARM的情况如何呢？这个问题的操作数大小是多少,是大小相同还是输入大小加倍？您是否愿意执行硬件无法执行的乘法(没有溢出)？您是在编写编译器库并尝试确定是否可以将操作数提供给硬件以提高速度,或者是否必须在没有硬件乘法的情况下执行数学运算.如果你编译操作数,你会得到哪种东西,编译器库会在执行乘法之前尝试将操作数强制转换,当然,这取决于编译器及其库.并且它将使用位技巧确定的计数来使用硬件乘法或软件.

我的目标是显示二进制乘法如何以易于理解的形式工作,这样您就可以通过查找每个操作数中单个位的位置来查看所需的最大存储量.现在你在每个操作数中找到该位的速度有多快.如果您正在寻找最小存储要求而不是最大值,这是一个不同的故事因为涉及两个操作数中的每一个有效位而不是每个操作数一位,您必须进行乘法以确定最小存储.如果您不关心最大或最小存储,则必须进行乘法运算并查找高于定义的溢出限制的非零值,或者如果您有时间或硬件则使用除法.

你的标签意味着你对浮点不感兴趣,浮点是一个完全不同的野兽,你不能将这些定点规则中的任何一个应用于浮点,它们不起作用.

Answer 2

检查其中一个是否小于最大值除以另一个。（所有值均视为绝对值）。

2 的补集几乎与它无关，因为如果 x*(2 ⁿ - x)>2 ^M等于 (x*2 ⁿ - x ² )>2 ^M或 x ² < (x *2 ⁿ - 2 ^M），所以无论如何你都必须比较溢出的数字（x ²可能会溢出，而结果可能不会）。