我用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++中检测有符号溢出。


当前回答

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

其思想是,正是因为处理器会让值归零,而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};

其他回答

另一个有趣的工具是IOC: C/ c++的整数溢出检查器。

这是一个修补过的Clang编译器,它在编译时向代码添加检查。

输出如下所示:

CLANG ARITHMETIC UNDEFINED at <add.c, (9:11)> :
Op: +, Reason : Signed Addition Overflow,
BINARY OPERATION: left (int32): 2147483647 right (int32): 1

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

为了扩展Head Geek的答案,有一种更快的方法来执行addition_is_safe;

bool addition_is_safe(unsigned int a, unsigned int b)
{
    unsigned int L_Mask = std::numeric_limits<unsigned int>::max();
    L_Mask >>= 1;
    L_Mask = ~L_Mask;

    a &= L_Mask;
    b &= L_Mask;

    return ( a == 0 || b == 0 );
}

这使用了机器架构安全,64位和32位无符号整数仍然可以正常工作。基本上,我创建了一个掩码,它将屏蔽除最重要的位外的所有内容。然后,对两个整数进行掩码,如果其中任何一个没有设置该位,则加法是安全的。

如果在某个构造函数中预初始化掩码,这将更快,因为它永远不会改变。

从C23开始,标准头文件<stdckdint.h>提供了以下三个类函数宏:

bool ckd_add(type1 *result, type2 a, type3 b);
bool ckd_sub(type1 *result, type2 a, type3 b);
bool ckd_mul(type1 *result, type2 a, type3 b);

其中type1, type2和type3是任何整数类型。这些函数分别以任意精度对a和b进行加、减或乘,并将结果存储在*result中。如果结果不能由type1精确表示,则函数返回true("计算已溢出")。(任意精确是一种错觉;计算速度非常快,自20世纪90年代初以来几乎所有可用的硬件都可以在一个或两个指令内完成。)

重写OP的例子:

unsigned long b, c, c_test;
// ...
if (ckd_mul(&c_test, c, b))
{
    // returned non-zero: there has been an overflow
}
else
{
    c = c_test; // returned 0: no overflow
}

C_test包含所有情况下可能溢出的乘法结果。

早在C23之前,GCC 5+和Clang 3.8+就提供了以同样方式工作的内置程序,除了结果指针是最后传递而不是第一个传递:__builtin_add_overflow, __builtin_sub_overflow和__builtin_mul_overflow。这些也适用于小于int的类型。

unsigned long b, c, c_test;
// ...
if (__builtin_mul_overflow(c, b, &c_test))
{
    // returned non-zero: there has been an overflow
}
else
{
    c = c_test; // returned 0: no overflow
}

Clang 3.4+引入了具有固定类型的算术溢出内置函数,但它们的灵活性要低得多,而且Clang 3.8现在已经可用很长时间了。如果你需要使用__builtin_umull_overflow,尽管有更方便的更新选项。

Visual Studio的cl.exe没有直接的等价物。对于无符号加减法,包括<intrin.h>将允许您使用addcarry_uNN和subborrow_uNN(其中NN是位数,如addcarry_u8或subborrow_u64)。他们的签名有点迟钝:

unsigned char _addcarry_u32(unsigned char c_in, unsigned int src1, unsigned int src2, unsigned int *sum);
unsigned char _subborrow_u32(unsigned char b_in, unsigned int src1, unsigned int src2, unsigned int *diff);

C_in /b_in是输入的进位/借位标志,返回值是输出的进位/借位。它似乎没有符号运算或乘法的等价物。

另外,Clang for Windows现在已经可以投入生产(对于Chrome来说已经足够好了),所以这也是一个选择。

我看到你用的是无符号整数。根据定义,在C中(我不了解c++),无符号算术不会溢出…所以,至少对C来说,你的观点是没有意义的:)

对于有符号整数,一旦出现溢出,就会发生未定义行为(UB),程序可以做任何事情(例如:使测试不确定)。

#include <limits.h>

int a = <something>;
int x = <something>;
a += x;              /* UB */
if (a < 0) {         /* Unreliable test */
  /* ... */
}

要创建一个符合要求的程序,您需要在生成溢出之前测试溢出。该方法也可以用于无符号整数:

// For addition
#include <limits.h>

int a = <something>;
int x = <something>;
if (x > 0 && a > INT_MAX - x) // `a + x` would overflow
if (x < 0 && a < INT_MIN - x) // `a + x` would underflow

// For subtraction
#include <limits.h>
int a = <something>;
int x = <something>;
if (x < 0 && a > INT_MAX + x) // `a - x` would overflow
if (x > 0 && a < INT_MIN + x) // `a - x` would underflow

// For multiplication
#include <limits.h>

int a = <something>;
int x = <something>;
// There may be a need to check for -1 for two's complement machines.
// If one number is -1 and another is INT_MIN, multiplying them we get abs(INT_MIN) which is 1 higher than INT_MAX
if (a == -1 && x == INT_MIN) // `a * x` can overflow
if (x == -1 && a == INT_MIN) // `a * x` (or `a / x`) can overflow
// general case
if (x != 0 && a > INT_MAX / x) // `a * x` would overflow
if (x != 0 && a < INT_MIN / x) // `a * x` would underflow

对于除法(INT_MIN和-1特殊情况除外),不可能超过INT_MIN或INT_MAX。