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

10/4/2018

缘起

最近刷了一些 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 答案的基础上按自己的理解稍做了一点修改:

结尾

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