对于两个位数相同的有符号整数，如何判断它们相乘后的结果不会溢出？
在《深入理解计算机系统》（第3版）的练习题2.35中，教材给出了这样的函数：
/* Determine whether arguments can be multiplied without overflow */
int tmult_ok(int x, int y) {
int p = x*y;
/* Either x is zero, or dividing p by x gives y */
return !x || p/x == y;
}
这个函数功能的正确性直观上似乎显然易见。但需要注意的是，上面C语言代码中的除法运算是整数除法，而不是数学中的除法，条件p/x == y并不能推导出p == x * y。例如，当x与y均为非负整数时，只要满足，条件
p/x == y一定返回true。
我们仍然需要坚实的依据，来证明这个符合直觉的判断条件是正确的。我们记乘数为与
，它们的真实乘积为
，补码乘积为
。设
、
和
的二进制表示为
位。由于计算机是无法得知真实乘积的值，我们只能根据补码乘积和真实乘积之间存在的某种关系，来间接判断是否发生了乘法溢出。
补码乘积与真实乘积的关系
我们从乘积的二进制表示切入分析。可以用长度为
位的二进制补码表示，而
的二进制表示长度为
位。我们可以先尝试用高
位和低
位的数表示
，看看能发现什么。
设表示
的低
位代表的无符号数数值，
表示
的高
位代表的补码数值。于是
可以用
和
表示为
注意，补码乘积的二进制表示，实际上就是
的数值低
位的二进制表示。根据原码和补码之间的数值转换关系，
可以用
表示为
其中，是的
的二进制表示的最高位。将这个式子代入
，可以得到
至此，我们已经得到了补码乘积与真实乘积的关系，可以表示成
与
的整数倍的和。我们不考虑整数倍内部的细节，将
记作
，可以将上式写作
根据这个表达式可以看出：
- 当
时，有
，此时补码乘积与真实乘积的值相等，乘法必然没有溢出
- 当
时，
包含了
的整数倍，无法用长度
位的二进制数表示，此时乘法必然溢出
由此，乘法溢出的问题，就转换成了判断是否为0的问题。
值的间接判断
在开头我们提到，p/x在C语言中是整数除法，我们可以先用数学公式表示这一整除关系：
其中，对应
整除
的值，
为余数。
我们分析一下这一整除关系与中
值之间的联系：
- 当
整除
等于
，即
中
且
时，代入
可以得到
当且仅当 - 当
根据整除关系
至此，我们已经成功证明了整除
等于
是乘法没有发生溢出的充分必要条件，即
- 当条件
p/x == y成立时，x*y一定没有发生溢出 - 反之，当
x*y没有发生溢出时，一定有条件p/x == y成立。
代码中的判断条件p/x == y，可以作为判断乘法是否溢出的可靠依据。
总结
在上述证明过程中，我们从真实乘积的二进制表示入手，确定了真实乘积与补码乘积之间的关系，将判断乘法溢出的问题转化为另一个等价问题，最后结合整数除法的性质给出了等价问题的解决方案，证明了条件p/x == y判断乘法溢出的正确性。
