多重溢出测试

Question

如何正确检查整数乘法中是否发生溢出？

int i = X(), j = Y();
i *= j;

如何检查溢出,给定值i,j并且它们的类型？请注意,对于有符号和无符号类型,检查必须正常工作.可以假定这两个i和j是同一类型的.也可以假设在编写代码时已知类型,因此可以为签名/未签名的案例提供不同的解决方案(不需要模板杂耍,如果它在"C"中工作,则是奖励).

编辑:@pmg的答案是正确的.我暂时无法绕过它的简单,所以我会在这里与你分享.假设我们要检查:

i * j > MAX

但我们无法真正检查,因为i * j会导致溢出,结果将是不正确的(并且总是小于或等于MAX).所以我们这样修改它:

i > MAX / j

但这并不完全正确,因为在分工中,涉及到一些四舍五入.相反,我们想知道这个结果:

i > floor(MAX / j) + float(MAX % j) / j

因此我们有了除法本身,它被整数算术隐含地向下舍入(在floor那里是无操作,仅作为例证),并且我们在前一个不等式中缺少了除法的其余部分(其评估为更少)比1).

假设i和j是两个数字在极限,如果它们中的任何一个增加1,将发生溢出.假设其中没有一个是零(在这种情况下,没有溢出会发生无论如何),两者(i + 1) * j和i * (j + 1)均超过1 + (i * j).因此,我们可以安全地忽略除法的舍入误差,该误差小于1.

或者,我们可以重新组织:

i - floor(MAX / j) > float(MAX % j) / j

基本上,这告诉我们i - floor(MAX / j)必须大于一个[0, 1)区间中的数字.这可以写成:

i - floor(MAX / j) >= 1

因为1就在间隔之后.我们可以改写为:

i - floor(MAX / j) > 0

或者:

i > floor(MAX / j)

所以我们已经证明了简单测试和浮点版本的等价性.这是因为除法不会导致显着的舍入误差.我们现在可以使用简单的测试,从此过上幸福的生活.

Answer 1

你不能事后测试.如果乘法溢出,则会触发未定义的行为,这会导致测试无法确定.

你需要在进行乘法之前进行测试

if (INT_MAX / x > y) /* multiplication of x and y will overflow */;