如何检测 2 的补码乘法溢出？

在我正在阅读的一本书中，以下函数用于确定 2 的补码整数乘法溢出。

int tmult_ok(int x, int y) {
int p = x*y;
return !x || p/x == y;
}

虽然这有效，但我如何证明它在所有情况下的正确性？ 当发生溢出时如何确保 p != x*y ？

这是我的理解：

1. 当您将 2 个大小为“w 位”的整数相乘时，结果可以是 2w 位。
2. 计算会截断高阶 w 位。所以我们剩下低阶 w 位。 3.假设 P = 最低 w 位
3. 然后，我们需要证明（P/x != y）和（P/y !=x）当发生溢出时。
4. 我的困惑就在这里。当没有溢出时，你怎么能说(P/x !=y)呢？即使存在溢出，P 的位模式除以 x 也可能产生 y 吗？

tmult_ok(x, y)随时失败x*y in int p = x*y;就这样溢出了未定义的行为 (UB).
它也失败了像这样的极端情况tmult_ok(INT_MIN, -1)为了同样的原因。
它不能便携地“工作”。

另一种选择（和其他为 /、-、+ https://codereview.stackexchange.com/a/93699/29485) 不依赖于 2 的补码。请注意，这会返回相反的结果tmult_ok().

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
}

当发生溢出时如何确保 p != x*y ？

可移植代码不能。对于 C 中的有符号整数数学，溢出为 UB。代码应该在不首先执行乘法的情况下检测潜在的溢出。@Quentin https://stackoverflow.com/questions/50684187/how-do-you-detect-2s-complement-multiplication-overflow/50684646#comment88378418_50684187 @尤金·什。 https://stackoverflow.com/questions/50684187/how-do-you-detect-2s-complement-multiplication-overflow/50684646#comment88379482_50684187

我如何证明它在所有情况下的正确性？

使用 2x 宽数学形成参考测试。如果int是32位的，比较一下tmult_ok()使用 64 位数学进行乘法，并查看乘积是否在范围内。@rici https://stackoverflow.com/questions/50684187/how-do-you-detect-2s-complement-multiplication-overflow/50684646#comment88379605_50684187

int tmult_ok_ll(int x, int y) {
  long long prod = x;
  prod *= y;
  return (prod >= INT_MIN && prod <= INT_MAX);
}

尝试所有组合是一种蛮力方法 - 对于 32 位来说可能太长int.

尝试所有组合的子集，对于每个x,y,try INT_MIN, INT_MIN-1, INT_MIN-2, -2,-1, 0, 1, 2, , INT_MAX-1, INT_MAX。 (10*10测试)

也是所有组合的子集，每个值 +/- 在 2 以内sqrt(INT_MAX)。 (10*10测试)

还有几百万个随机值int范围将是谨慎的。

这可能还不够，但如果代码通过了这一点，那么剩下的极端情况就很少了——这非常依赖于您的源代码。

也可以看看@埃里克·波斯特皮斯基尔 https://stackoverflow.com/questions/50684187/how-do-you-detect-2s-complement-multiplication-overflow?noredirect=1#comment88380237_50684646