我用c++写了一个程序来寻找ab = C的所有解,其中a, b和C一起使用所有的数字0-9,只使用一次。程序循环遍历a和b的值,并每次对a、b和ab运行数字计数例程,以检查是否满足数字条件。

但是,当ab超出整数限制时,会产生伪解。我最终使用如下代码来检查这个:

unsigned long b, c, c_test;
...
c_test=c*b;         // Possible overflow
if (c_test/b != c) {/* There has been an overflow*/}
else c=c_test;      // No overflow

是否有更好的方法来测试溢出?我知道有些芯片有一个内部标志,在溢出发生时设置,但我从未见过通过C或c++访问它。


注意,有符号int溢出在C和c++中是未定义的行为,因此您必须在不实际引起它的情况下检测它。对于加法前的有符号整型溢出,请参见在C/ c++中检测有符号溢出。


当前回答

对于无符号整数,只需检查结果是否小于其中一个参数:

unsigned int r, a, b;
r = a + b;
if (r < a)
{
    // Overflow
}

对于有符号整数,可以检查参数和结果的符号。

不同符号的整数不能溢出,相同符号的整数只有在结果为不同符号时才会溢出:

signed int r, a, b, s;
r = a + b;
s = a>=0;
if (s == (b>=0) && s != (r>=0))
{
    // Overflow
}

其他回答

mozilla::CheckedInt<T>为整数类型T提供溢出检查的整数数学(使用clang和gcc上可用的编译器intrinsic)。该代码是在MPL 2.0下编写的,并且依赖于三个(integertypetrait .h, Attributes.h和Compiler.h)其他仅针对标头的非标准库标头以及mozilla特定的断言机制。如果导入代码,可能需要替换断言机制。

这里有一个非常快速的方法来检测溢出,至少是加法,这可能会为乘法、除法和乘方提供线索。

其思想是,正是因为处理器会让值归零,而C/ c++是从任何特定的处理器抽象出来的,你可以:

uint32_t x, y;
uint32_t value = x + y;
bool overflow = value < (x | y);

这既确保了如果一个操作数为零,另一个操作数为零,则不会错误地检测到溢出,而且比前面建议的许多NOT/XOR/ and /test操作要快得多。

正如所指出的,这种方法虽然比其他更精细的方法更好,但仍然是可优化的。以下是包含优化的原始代码的修订:

uint32_t x, y;
uint32_t value = x + y;
const bool overflow = value < x; // Alternatively "value < y" should also work

一种更有效、更廉价的检测乘法溢出的方法是:

uint32_t x, y;
const uint32_t a = (x >> 16U) * (y & 0xFFFFU);
const uint32_t b = (x & 0xFFFFU) * (y >> 16U);
const bool overflow = ((x >> 16U) * (y >> 16U)) +
    (a >> 16U) + (b >> 16U);
uint32_t value = overflow ? UINT32_MAX : x * y;

这将导致UINT32_MAX溢出,或乘法的结果。在这种情况下,允许对有符号整数进行乘法运算是严格未定义的行为。

值得注意的是,这使用部分Karatsuba方法乘法分解来计算64位乘法的高32位,以检查是否应该设置它们中的任何一个,以了解32位乘法是否溢出。

如果使用c++,你可以把这个转换成一个简洁的小lambda来计算溢出,这样检测器的内部工作就被隐藏了:

uint32_t x, y;
const bool overflow
{
    [](const uint32_t x, const uint32_t y) noexcept -> bool
    {
        const uint32_t a{(x >> 16U) * uint16_t(y)};
        const uint32_t b{uint16_t(x) * (y >> 16U)};
        return ((x >> 16U) * (y >> 16U)) + (a >> 16U) + (b >> 16U);
    }(x, y)
};
uint32_t value{overflow ? UINT32_MAX : x * y};

在C中捕获整数溢出指出了一种比CERT讨论的更通用的解决方案(就处理的类型而言,它更通用),即使它需要一些GCC扩展(我不知道它们有多广泛的支持)。

我需要为浮点数回答同样的问题,在浮点数中位屏蔽和移位看起来没有希望。我确定的方法适用于有符号和无符号,整数和浮点数。即使没有更大的数据类型可以用于中间计算,它也可以工作。对于所有这些类型,它不是最有效的,但因为它确实适用于所有类型,所以值得使用。

有符号溢出测试,加减法:

Obtain the constants that represent the largest and smallest possible values for the type, MAXVALUE and MINVALUE. Compute and compare the signs of the operands. a. If either value is zero, then neither addition nor subtraction can overflow. Skip remaining tests. b. If the signs are opposite, then addition cannot overflow. Skip remaining tests. c. If the signs are the same, then subtraction cannot overflow. Skip remaining tests. Test for positive overflow of MAXVALUE. a. If both signs are positive and MAXVALUE - A < B, then addition will overflow. b. If the sign of B is negative and MAXVALUE - A < -B, then subtraction will overflow. Test for negative overflow of MINVALUE. a. If both signs are negative and MINVALUE - A > B, then addition will overflow. b. If the sign of A is negative and MINVALUE - A > B, then subtraction will overflow. Otherwise, no overflow.

签名溢出测试,乘法和除法:

Obtain the constants that represent the largest and smallest possible values for the type, MAXVALUE and MINVALUE. Compute and compare the magnitudes (absolute values) of the operands to one. (Below, assume A and B are these magnitudes, not the signed originals.) a. If either value is zero, multiplication cannot overflow, and division will yield zero or an infinity. b. If either value is one, multiplication and division cannot overflow. c. If the magnitude of one operand is below one and of the other is greater than one, multiplication cannot overflow. d. If the magnitudes are both less than one, division cannot overflow. Test for positive overflow of MAXVALUE. a. If both operands are greater than one and MAXVALUE / A < B, then multiplication will overflow. b. If B is less than one and MAXVALUE * B < A, then division will overflow. Otherwise, no overflow.

注意:MINVALUE的最小溢出由3处理,因为我们取的是绝对值。然而,如果 ABS(MINVALUE) > MAXVALUE,那么我们将会有一些罕见的假阳性。

下溢测试类似,但涉及EPSILON(大于零的最小正数)。

CERT开发了一种新方法,使用“as-if”无限范围(AIR)整数模型来检测和报告有符号整数溢出、无符号整数包装和整数截断。CERT已经发布了一份描述该模型的技术报告,并生成了一个基于GCC 4.4.0和GCC 4.5.0的工作原型。

AIR整数模型产生的值与使用无限范围整数所获得的值相等,或者导致违反运行时约束。与之前的整数模型不同,AIR整数不需要精确的陷阱,因此不会破坏或抑制大多数现有的优化。