给你一个任务,开发函数tmult_ok的代码,该函数会判断两个参数相 乘是否会产生溢出。下面是你的解决方案:
/* 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 I I p/x == y; }
你用X和y的很多值来测试这段代码,似乎都工作正常。你的同事挑战你,说: “如果我不能用减法来检验加法是否溢出(参见练习题2. 31),那么你怎么能用除法来 检验乘法是否溢出呢?”
按照下面的思路,用数学推导来证明你的方法是对的。首先,证明:x = 0的情况 是正确的。另外,考虑ω位数字x(x≠0)^、y、p和q,这里p是x和y补码乘法的结果,而q是p除以x的结果。
1)说明x和y的整数乘积x • y,可以写成这样的形式:x • y = p+t2ω,其中, t≠0当且仅当p的计算溢出。
2)说明p可以写成这样的形式:p=x • q+r,其中|r|<|x|。
3)说明q = y当且仅当r = t = 0