潜在溢出的乘法运算后再进行除法验证是否存在问题？

Question

假设我有两个size_t变量，我需要将它们相乘，并将结果作为size_t返回。

size_t first = ...;
size_t second = ...;
size_t result = first * second;

它们可能会溢出，所以我需要进行检查。

“规范”方式是先通过除法检查是否可以进行乘法：

if( second != 0 && first > ((size_t)-1) / second ) {
   //handle overflow
}
//proceed with computing first * second

看似不太“干净”的方法是先乘法，然后再用除法检查结果：

size_t result = first * second;
if( second != 0 && result / second != first )
   //handle overflow
}

然而，由于无符号数的乘法会通过环绕0来“安全地溢出”，因此这个方法可以正常工作，并且看起来与前面的代码（先检查再相乘）等价。

第二个代码有潜在的问题吗？它是否始终和第一个代码一样好？

- sharptooth

---

这个问题让我想起了几天前看到的这条推文。 - Borgleader

并不是每个人都能意识到-1会始终转换为最大无符号值。 - Shafik Yaghmour

我唯一看到的是在第二个例子中你无条件地进行了乘法，这可能会增加额外的开销。 - NathanOliver

分支预测失败的代价现在可能比乘法还要高。 - Alan Stokes

如何在C/C++中检测整数溢出？ - phuclv

Answer 1

从数学角度来看，如果

((a*b) mod (2^n)) / b == a  

如果对于一些溢出值成立（这意味着a和b都不为0），那么这将是一个问题。
根据Wolfram Alpha，对于溢出，它永远不会成立，因为要得到结果，结果变量n的位长必须大于所需的a*b的位长(log[2](a*b))。

从代码角度来看，我现在也想不出任何问题。

- deviantfan

Answer 2

我认为您不仅需要检查除法，还应该检查余数：

if( second != 0 && (result / second != first || (result % second) != 0))

如果c=b*a，则只有一个c的值使得c/b=a。试图用除以b的任何其他值来产生a都不会成功。

然而，这不是整数数学，而是实数数学。由于整数除法四舍五入，因此该公式在技术上不成立，因为只要b至少为2，对于某些c的值，(c+1)/b也将是a。

- Sam Varshavchik

---

他试图测试溢出，而不是乘法实现中的错误。是否存在需要进行 % 测试的情况？ - ugoren

Answer 3

你上面提到的第一种方法是错误的。将负数转换为无符号类型是不正确的，会导致未定义行为。

第二种方法，唯一使得乘积与两个因数不同的方式是在中间发生溢出，这种方法是正确的，但是溢出可能会导致未定义行为，因此也是不正确的（你暗示溢出将导致取模运算的乘法溢出，而结果确实是未定义的）。

检查可能溢出的一种方法是：

if (MAX_UINT / one_of_the_factors < the_other_factor) ...

这是完全定义的，并且允许您以可移植的方式在执行实际乘法之前检测溢出。

- Luis Colorado

---

C++03标准21.3.6中对npos的定义为：static const size_type npos = -1，因此我不确定这个技巧是否会导致未定义行为。 - sharptooth

我的回答中没有特别涉及到C++03。我尽可能地保证了代码的可移植性，因为问题是用C、C++、数字和乘法标签来描述的。此外，size_t并不是C++特有的类型。真正的情况是，将负的有符号整数（无论类型是什么）转换为无符号整数在任何一种语言中都是未定义的行为。C使用esize_t来支持有符号性。 - Luis Colorado