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

Question

我想将两个数字相乘，并检测是否存在溢出。最简单的方法是什么？

Answer 1

两个 32 位数字相乘得到 64 位答案，两个 8 得到 16，等等。二进制乘法只是移位和加法。因此，如果您说两个 32 位操作数和操作数 A 中设置的位 17 以及操作数 b 中设置的高于 15 或 16 的任何位，您将溢出 32 位结果。位 17 左移 16 是位 33 添加到 32。

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

编辑

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

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

0b100 *
0b100 

就像学校中的十进制数学一样，您可以从下部操作数的最低有效位开始，并将其与上部操作数中的所有位置相乘，但二进制除外只有两个选择，您乘以零意味着您不必添加到结果中，或者您乘以一意味着您只需移位和添加，不需要像十进制那样的实际乘法。

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

将各列相加，答案为 0b10000 与

十进制数学相同，百位列中的 1 表示复制顶部数字并添加两个零，它在任何其他基数中也同样有效。所以 0b100 乘以 0b110 是 0b1000，第二列中的 1 复制并添加一个零 + 0b10000 第三列中的 1 复制并添加两个零 = 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 加一，将负数视为最高有效的 0 加一。

-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 位来安全存储答案。所以这条规则可以回答 2 补码数学问题。

如果您的问题是准确确定溢出，然后速度是次要的，那么，对于某些系统来说，对于您所做的每一次乘法，它都会非常慢。如果这是您问的问题，为了恢复一些速度，您需要针对语言和/或处理器进行更好的调整。如果可以的话，将最大的操作数加倍，并检查结果大小以上的非零位，或者使用除法和比较。如果您无法将操作数大小加倍，请进行除法和比较。在除法之前检查是否为零。

实际上，您的问题也没有指定您正在谈论的溢出大小。好的旧 8086 16 位乘以 16 位给出 32 位结果（硬件），它永远不会溢出。一些ARM有乘法，32位乘32位，32位结果，容易溢出。这个问题的操作数的大小是多少，它们的大小是相同的还是输入大小的两倍？您愿意执行硬件无法执行的乘法（不会溢出）吗？您是否正在编写编译器库并尝试确定是否可以将操作数提供给硬件以提高速度，或者是否必须在没有硬件乘法的情况下执行数学运算。如果你向上转换操作数，编译器库会在进行乘法之前尝试将操作数向下转换，这当然取决于编译器及其库。它将使用计数位技巧来确定使用硬件乘法还是软件乘法。

我的目标是展示二进制乘法如何以易于理解的形式工作，以便您可以通过查找每个操作数中单个位的位置来了解需要多少最大存储空间。现在，你能多快地找到每个操作数中的那个位就是诀窍。如果您正在寻找最小存储要求而不是最大存储要求，那就是另一回事了，因为涉及两个操作数中的每一个有效位，而不仅仅是每个操作数一位，您必须进行乘法以确定最小存储。如果您不关心最大或最小存储空间，则只需进行乘法并查找高于定义的溢出限制的非零值，或者如果您有时间或硬件，则可以使用除法。

您的标签暗示您对浮点不感兴趣，浮点是完全不同的野兽，您不能将任何这些定点规则应用于浮点，它们不起作用。

Answer 2

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

2 的补集几乎与它没有任何关系，因为如果 x*(2ⁿ - x)>2^M 则乘法溢出，等于 (x*2 ⁿ - x²)>2^M，或 x² < (x*2ⁿ - 2^M)，因此您无论如何都必须比较溢出的数字（x² 可能会溢出，而结果可能会不是）。

Answer 3

我想将两个数字（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
}

---

这是最简单的方法吗？
也许吧，但它是完整的，可以处理我所知道的所有情况 - 包括罕见的非 2 补码。

Answer 4

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

如果该类型已经是最大的，则检查其中一个是否小于最大值除以另一个。但不要取绝对值！相反，您需要为每个符号组合 negneg、pospos 和 posneg 提供单独的比较逻辑（negpos 显然可以简化为 posneg，而 pos pos 可能会减少为 neg*neg）。首先测试 0 个参数以允许安全除法。

有关实际代码，请参阅 commons-math 2 的 MathUtils 类的 Java 源代码，或 ArithmeticUtils of commons-math 3。查找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 5

Pavel Shved 解决方案的替代方案...

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

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

希望这有帮助。

Answer 6

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

此处包含测试用例的完整示例

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