如何检测两个二进制补码整数相乘时的溢出？

Question

如何检测两个二进制补码整数相乘时的溢出？

algorithmoverflowinteger-overflowtwos-complement

21

我想要将两个数字相乘，同时检测是否发生了溢出。最简单的方法是什么？

- Lazer

1

请参考以下与C/C++整数溢出有关的问题：https://dev59.com/3nVC5IYBdhLWcg3wvTxa - Christian Semrau

6个回答

3

检查一个值是否小于另一个值除以最大值。(所有的值都是绝对值)。

二进制补码并没有太多关系，因为如果 x*(2ⁿ - x)>2^M，即 (x*2ⁿ - x²)>2^M, 或者 x² < (x*2ⁿ - 2^M)，这意味着您仍需要比较溢出的数字(x² 可能会溢出，而结果不会)。

- P Shved

1

2的补码在一个因子为负数，另一个因子为正数时会产生差异，因为结果可能是MIN_VALUE，其绝对值比MAX_VALUE多1。因此，您需要针对每个符号组合进行单独的比较。我不明白你的x*(2**n-x)>2**M示例是从哪里来的。 - Christian Semrau

@Christian，我的例子来自于试图将所有可以通过位移计算的东西分组到不等式的一部分中，而将其他所有东西分组到另一部分中。 - P Shved

1

我想要相乘两个（2的补码）数字，并检测是否发生了溢出。最简单的方法是什么？

许多语言在溢出发生后不指定有效检查，因此需要进行先前的测试。

对于某些类型，可能不存在更宽的整数类型，因此一般解决方案应限制为单个类型。

下面的方法（Ref）仅需要比较和已知整数范围的限制。如果将发生乘积溢出，则返回1，否则返回0。

int is_undefined_mult1(int a, int b) {
  if (a > 0) {
    if (b > 0) {
      return a > INT_MAX / b;       // a positive, b positive
    }
    return b < INT_MIN / a;         // a positive, b not positive
  }
  if (b > 0) {
    return a < INT_MIN / b;         // a not positive, b positive
  }
  return a != 0 && b < INT_MAX / a; // a not positive, b not positive
}

这是最简单的方法吗？也许是，但它是完整的并且处理我所知道的所有情况，包括罕见的非二补数。

- chux - Reinstate Monica

1

如果您的数字不是最大整数数据类型，则可以将它们转换为该类型，进行乘法运算并与数字原始类型的最大值进行比较。例如，在Java中，当乘以两个int时，您可以将它们转换为long，并将结果与Integer.MAX_VALUE或Integer.MIN_VALUE（取决于符号组合）进行比较，然后将结果转换回int。

如果类型已经是最大的，则检查一个数字是否小于另一个数字的最大值除以它自己。但不要取绝对值！相反，您需要为每个符号组合negneg、pospos和posneg（显然可以将negpos缩减为posneg，而pospos可能会缩减为neg*neg）编写单独的比较逻辑。首先测试0个参数以允许安全分割。

如需实际代码，请参见commons-math 2的MathUtils类或ArithmeticUtils of commons-math 3的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);
}

- Christian Semrau

假设每个整数类型的宽度至少是前一个类型的两倍，那么你可能只需要将它们强制转换。在C或C++中不能保证这一点，但通常是成立的。 - Steve Jessop

1

不必处理各种符号组合，检测操作是否可逆(即，在检测b != 0后，(a * b) / b == a)是否足够？ - jamesdlin

@james 在 C/C++ 中，你无法这样做，因为溢出的结果未定义且取决于硬件（可能会环绕或抛出异常），因此你不能在乘法后便携地检测溢出。在 Java 中，结果是定义好的，乍一看，你的建议应该可以工作。但不幸的是，对于 a=Long.MIN_VALUE, b=-1L，它并不起作用。 - Christian Semrau

链接腐败... http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/MathUtils.java？view=markup - user246672

谢谢，@Barry。链接已更新。 - Christian Semrau

0

如果您选择的语言是汇编语言，那么您应该能够检查溢出标志。如果不行，您可以编写一个自定义的汇编程序，如果设置了溢出标志，则设置一个变量。

如果这不可接受，您可以找到两个值（绝对值）的最高有效位。如果它们相乘后的和超过整数（或无符号整数）的位数，则会发生溢出。

希望这可以帮助到您。

- Sparky

最后一个似乎不正确。给定无符号数字，4表示100（2进制）或3位，但是即使位的总和为6，4 * 4也不会溢出5位寄存器。但反过来就不一样了 - 如果位的总和小于n，则不可能溢出。 - Phil

只是添加位索引可能只能给出一些线索，因为正如@Phil所指出的那样，100_2 * 100_2 = 10000_2不会溢出5位值，但是111_2 * 111_2 = 110001_2会溢出。 - Christian Semrau

你说得完全正确——位索引能提供的最好的只是一个线索。在将其作为解决方案之前，我应该更加仔细和专注。 - Sparky

0

在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));
}

这里有完整的测试用例示例

以上方法的好处是不需要将类型转换为更大的类型，因此该方法可以适用于更大的整数类型。

- user246672

2

没有测试你的代码，我认为有一个角落情况被忽略了，即当a是2的幂次方而b是2的负幂次方时，它们的乘积是INT_MIN。例如：a=2, b=-INT_MIN/2。 - Christian Semrau

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- old_timer · Accepted Answer

两个32位数字相乘的结果为64位，两个8位的数字相乘则为16位，等等。二进制乘法就是移位和加法。因此如果有两个32位操作数，操作数A的第17位设置为1，并且操作数B的15或16位以上任意一位被设置为1，则会导致32位结果溢出。将第17位向左移动16位后，得到的是第33位加上32位。

因此，问题再次是你的输入和输出大小是多少，如果结果大小相同，那么你必须找到两个操作数中最高位的1，将这些位置相加，如果结果大于你的结果空间，则会溢出。

编辑：

是的，将两个3位数字相乘将产生一个5位数字或6位数字（如果在加法中有进位）。同样，2位和5位数字可以产生6位或7位数字，等等。如果这个问题的原因是为了查看你的结果变量是否有足够的空间来存储答案，那么这个解决方案将适用于大多数语言和大多数处理器，并且相对较快。它在某些处理器上可以显著提高速度，在其他处理器上可能会显著降低速度。通常情况下（当然取决于如何实现），只需查看操作数中的位数就可以获得通用的快速解决方案。如果您可以在语言或处理器内部进行操作，则将最大操作数的大小加倍是一个安全的选择。除法非常昂贵（缓慢），大多数处理器甚至没有除法，更不要说任意加倍的操作数大小了。当然最快的方式是转换为汇编语言执行乘法，并查看溢出位（或将其中一个结果寄存器与零进行比较）。如果您的处理器不能在硬件上执行乘法，则无论您做什么，它都会变得很慢。尽管汇编语言是迄今为止最快且具有最准确的溢出状态，但我猜测它不是这篇文章的正确答案。

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

0b100 * 0b100

就像学校里的十进制数学一样，你（可以）从较低的操作数开始处理最低有效位，将其与上操作数中的所有位置相乘。但是，在二进制中只有两种选择：你可以将一个数字乘以零，这意味着不需要将其添加到结果中；或者你可以将一个数字乘以一，这意味着你只需要移位和相加，而不需要实际的乘法，这与十进制数学中的做法不同。

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

将这些列加起来，答案为0b10000。与十进制数学中的百位上为1表示复制顶部数字并添加两个零相同，在任何其他进制中也是如此。因此，0b100乘以0b110等于0b1000，在第二列中为1，因此复制并添加一个零+0b10000，在第三列中为1，因此复制并添加两个零=0b11000。

这导致查看两个数字中最重要的位。 0b1xx * 0b1xx保证向答案添加了1xxxx，并且这是加法中最大的位位置，没有其他单个输入到最终加法具有该列填充或更重要的列填充。从那里，只需要更多的位，以防其他加起来的位引起进位。

这发生在最坏的情况下全部都是1，即0b111 * 0b111时。

0b00111 + 0b01110 + 0b11100

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

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

好吧，假设操作数为正值，则为真。如果您认为其中某些数字是负数，则会改变事情，但变化不大。

减去4乘以5，0b1111 ... 111100 * 0b0000 ... 000101 = -20或0b1111..11101100

表示负4需要4位，表示正5也需要4位（不要忘记符号位）。如果剥离所有符号位，则所需的结果为6位。

让我们看看4位的极端情况。

-8 * 7 算出的结果是 4+4=8 位，实际上是 7 位。 -1 * 7 算出的结果是 1+4=5 位，实际上是 4 位。 -8 * -8 算出的结果是 4+4=8 位，实际上是 8 位。 -1 * -1 算出的结果是 1+1=2 位，实际上是 3 位。 -1 * -8 算出的结果是 1+4=5 位，实际上是 5 位。 7 * 7 算出的结果是 4+4=8 位，实际上是 7 位。

这个规则适用于大多数情况，但对于 -1 * -1 这种情况需要注意，因为我们将 -1 视为一位，对于正数可以找到零加一。不管怎样，如果按照定义一个 4 位 * 4 位的机器，至少应该有 4 位的结果，我认为题目的意思是要确定是否需要使用超过 4 位的空间来安全存储答案。因此，这个规则可以回答这个问题，适用于二进制补码运算。

如果你的问题是精确地确定溢出并且速度其次，那么某些系统可能会非常慢，每次乘法都需要这样做。如果你这样问，为了提高一些速度，需要根据语言和/或处理器优化它。如果可以，将最大的操作数加倍，检查结果大小上方是否有非零位，或使用除法和比较。如果不能将操作数大小加倍，则使用除法和比较。在除法之前检查是否为零。

实际上，你的问题也没有说明你要考虑哪种类型的溢出。老式的 8086 16 位乘以 16 位的硬件可以得到 32 位的结果，永远不会溢出。那么像一些 ARM 处理器的乘法，32 位乘以 32 位的结果很容易溢出。对于这个问题，操作数的大小是多少？它们是相同大小还是双倍输入大小？您愿意执行硬件无法完成（而不会溢出）的乘法吗？如果您正在编写编译器库，并尝试确定是否可以将操作数馈送到硬件以获得速度，还是必须执行不带硬件乘法的计算。这是您转换操作数后的情况，编译器库将尝试在执行乘法之前将操作数转换回来，这取决于编译器及其库，它将使用统计位数的技巧来确定使用硬件乘法还是软件乘法。

我的目标是用一种易于理解的形式展示二进制乘法如何工作，以便您可以通过查找每个操作数中单个位的位置来确定需要多少最大存储空间。现在，您能够快速找到每个操作数中的那个位就是诀窍。如果您正在寻找最小存储要求而不是最大存储要求，那么情况就不同了，因为它涉及到两个操作数中所有显著位，而不仅仅是一个操作数中的一位。您必须进行乘法运算才能确定最小存储需求。如果您不关心最大或最小存储，则必须执行乘法并查找超出定义的溢出限制的非零值，或者使用除法（如果您有时间或硬件）。

您的标记表明您不对浮点数感兴趣，浮点数是完全不同的东西，您无法将任何这些定点规则应用于浮点数，它们不起作用。