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

Question

我想乘两个数字，并检测是否有溢出。什么是最简单的方法来做到这一点？

Answer 1

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

2的complementness几乎没有什么关系了，因为乘法溢出如果x *（2 ^Ñ - X）> 2 ^中号，其等于（X * 2 ^Ñ - X ）> 2 ^中号，或x <（X * 2 ^ñ - 2 ^中号），所以你必须四溢的数字反正比较（X 可能溢出，而结果可能不）。

Answer 2

替代帕维尔Shved的解决方案......

如果您选择的语言是汇编程序，那么你应该能够检查溢出标志。如果没有，你可以编写一个自定义的汇编程序例程，如果溢出标志被设置，它将设置一个变量。

如果这是不可接受的，您可以找到两个值（绝对值）中最重要的设置位。如果总和超过整数（或无符号）中的位数，那么如果它们相乘，则会发生溢出。

希望这会有所帮助。

Answer 3

如果你的号码不是来自最大的积分数据类型，那么你可能只是把它们放在一起，乘以并与数字原始类型的最大值进行比较。例如。在Java中，当将两个int相乘时，可以将它们投射到long并将结果与​​Integer.MAX_VALUE或Integer.MIN_VALUE（取决于符号组合）进行比较，然后将结果降至int。

如果类型已经是最大的，那么检查一个是否小于最大值除以另一个。但不要拿绝对的价值！相反，您需要为每个符号组合分别设置不同的比较逻辑。否则，pos可能会被归约为neg * neg。否则，pos可能会减少为neg * neg。首先测试0个参数以允许安全分割。

对于实际的代码，看到MathUtils类公地数学2，或commons-math 3ArithmeticUtils的Java源代码。寻找public static long mulAndCheck(long a, long b)。为正 a和b的情况下是

// check for positive overflow with positive a, positive b 
if (a <= Long.MAX_VALUE/b) { 
    ret = a * b; 
} else { 
    throw new ArithmeticException(msg); 
} 

Answer 4

乘以64位回答两个32位数字的结果，2 787-8得到16等二进制乘法被简单地转移并加入。所以如果你说操作数A中设置了两个32位操作数和位17，并且操作数b中设置了15或16以上的任何位，那么你将溢出一个32位结果。位17左移16位33加到32。

所以问题的另一个问题是输入的大小和结果的大小，如果结果是相同的大小，那么你必须找到两个操作数中最重要的一个，如果结果是比你的结果空间大，你会溢出。

EDIT

是乘以2个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位最坏情况。

因此，使用最高有效位（而不是保存值的寄存器的大小）的操作数大小决定了最差情况下的存储要求。

那么，假设积极的操作数是真的。如果你认为这些数字有些是负面的，它会改变事情，但不会太多。

减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加一，负最显著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位乘法的32位乘法器容易溢出的问题呢？这个问题的操作数的大小是多少，它们是相同的大小还是它们的输入大小的两倍？你是否愿意执行硬件无法做到的乘法（没有溢出）？你是否正在编写一个编译器库，并试图确定是否可以将操作数提供给硬件以提高速度，或者如果必须在没有硬件繁琐的情况下执行数学运算。如果你建立了操作数，那么你会得到哪种类型的东西，编译器库会尝试在执行乘法操作之前将操作数退回，这取决于编译器和它的库。并且它会使用计数比特技巧来决定使用硬件乘法还是软件。

我的目标是显示二进制乘法是如何以可消化的形式工作的，所以您可以通过查找每个操作数中单个位的位置来查看需要多少最大存储量。现在，您可以在每个操作数中找到那个位的速度有多快。如果您正在寻找不是最大值的最小存储需求，那是不同的故事，因为涉及两个操作数中的每个重要位而不是每个操作数一个位，所以必须进行乘法运算以确定最小存储。如果您不关心最大或最小存储量，则只需执行乘法操作，并在您定义的溢出限制之上寻找非零值，或者如果您有时间或硬件则使用除法值。

你的标签暗示你对浮点不感兴趣，浮点是一个完全不同的野兽，你不能将任何这些固定点规则应用于浮点，他们不工作。

Answer 5

在C，这里的一些成熟优化的代码来处理全方位的角落情况：

int 
would_mul_exceed_int(int a, int b) { 
    int product_bits; 

    if (a == 0 || b == 0 || a == 1 || b == 1) return (0); /* always okay */ 
    if (a == INT_MIN || b == INT_MIN) return (1); /* always underflow */ 

    a = ABS(a); 
    b = ABS(b); 

    product_bits = significant_bits_uint((unsigned)a); 
    product_bits += significant_bits_uint((unsigned)b); 

    if (product_bits == BITS(int)) { /* cases where the more expensive test is required */ 
    return (a > INT_MAX/b); /* remember that IDIV and similar are very slow (dozens - hundreds of cycles) compared to bit shifts, adds */ 
    } 
    return (product_bits > BITS(int)); 
} 

Full example with test cases here

上述方法的好处是它不需要铸造到更大类型，所以该方法可以在较大的整数类型上工作。