20

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

4

6 回答 6

12

将两个 32 位数字相乘得到 64 位答案，两个 8 得到 16，等等。二进制乘法只是移位和加法。因此，如果您在操作数 A 中设置了两个 32 位操作数和第 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 复制并在第三列中添加一个 0 + 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 位，表示正 5 需要 4 位（不要忘记符号位）。如果去掉所有符号位，我们的结果需要 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 是 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，你可以看到我把a 称为负一一位，对于加一的东西找到零加一。无论如何，我认为如果这是定义的 4 位 * 4 位机器，您至少会有 4 位结果，我将问题解释为我需要多于 4 位才能安全地存储答案。因此，此规则用于回答 2s 补码数学的问题。

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

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

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

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

于 2010-04-26T14:49:57.497 回答
3

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

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

于 2010-04-26T13:57:49.263 回答
1

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

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

MathUtils有关实际代码，请参阅commons-math 2 或commons-math 3ArithmeticUtils类的Java 源代码。寻找。正a 和 b的情况是public static long mulAndCheck(long a, long b)

// check for positive overflow with positive a, positive b
if (a <= Long.MAX_VALUE / b) {
    ret = a * b;
} else {
    throw new ArithmeticException(msg);
}
于 2010-04-26T14:43:04.010 回答
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));
}

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

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

于 2014-05-26T00:42:47.863 回答
0

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

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

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

希望这可以帮助。

于 2010-04-26T14:02:07.163 回答
0

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

这是最简单的方法吗？IDK，但它是完整的，可以处理我知道的所有案例。

于 2018-06-04T19:33:46.187 回答