多溢测试

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 */;

Answer 2

如果您的编译器的类型至少是int的两倍，那么您可以执行以下操作：

long long r = 1LL * x * y;
if ( r > INT_MAX || r < INT_MIN )
    // overflowed...
else
    x = r;

为了便携性，您应该STATIC_ASSERT( sizeof(long long) >= 2 * sizeof(int) );或类似的东西，但如果您担心填充位，则更极端！

Answer 3

试试这个

bool willoverflow(uint32_t a, uint32_t b) {
    size_t a_bits=highestOneBitPosition(a), 
    size_t b_bits=highestOneBitPosition(b);
    return (a_bits+b_bits<=32);
}

Answer 4

可以使用

除法查看溢出是否在事后发生。 在无符号值的情况下，如果 y！=0 并且： bool overflow_occured = (y!=0)? z/y!=x : false; （如果 y 等于零，则不会发生溢出）。 对于有符号值的情况，它有点棘手。
if(y!=0){ bool overflow_occured = (y<0 && x=2^31) | (y!=0 && z/y != x); } 我们需要表达式的第一部分，因为如果 x=-2^31 和 y=-1，第一个测试将失败。 在这种情况下，乘法溢出，但机器可能会给出 -2^31 的结果。 因此，我们单独对其进行测试。

对于 32 位值也是如此。 将代码扩展到 64 位大小写留给读者作为练习。