编程与数学(4): Check for integer overflow on multiplication

[shidenggui]

编程与数学(4): Check for integer overflow on multiplication

缘起

  最近刷了一些 leetcode 的题目，发现里面经常需要检测整数相乘是否溢出的问题，而答案给出的检测方法都比较特定而且不够方便。这让我想起了之前看 CSAPP 的时候，在第二章 Representing and Manipulating Information中有一道课后题，提供了一种检测乘法溢出的方法，简洁明了。因此在这里介绍下。

Check for integer overflow on multiplication

  题目来自于 CSAPP's Practice Problem 2.35:

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

  这里我们看到只要排除了 x 为 0 的情况后，如果 p / x != y 则溢出，否则即无溢出。这时候不禁要问一句

Why?

  下面给出证明，在 CSAPP 答案的基础上按自己的理解稍做了一点修改：

结尾

  判断的方法很简单，但是后面的论证却没那么容易。不过这便是不光知其然，还知其所以然的乐趣所在吧！

[Amadeusssssss]

感谢🙏