我应该如何检测无符号整数溢出？

16 浏览
0 Comments

我应该如何检测无符号整数溢出？

我在用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++访问它。

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

admin 更改状态以发布 2023年5月24日
0

2 答案

0 Comments

从C23开始，标准头文件提供以下三个类似函数的宏：

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
}

在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没有直接的等效物。对于无符号加法和减法，包括 将允许您使用 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 是进位/借位标志，返回值是输出的进位/借位标志。它似乎没有有符号操作或乘法的相当物。

否则，Windows的Clang现在已经可供生产使用（足够好用于Chrome），因此这也可能是一个选择。

0
0 Comments

我看到你使用了无符号整数。根据定义，在C语言中（我不知道C++），无符号算术不会溢出...所以，至少对于C语言，你的点是无用的。:)

使用有符号整数，一旦发生溢出，就会发生未定义行为（UB）（例如：使测试不确定）。

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

要创建符合规范的程序，您需要在生成所述溢出之前测试溢出。这种方法也可以用于无符号整数：

// For addition
#include 
int a = ;
int x = ;
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 
int a = ;
int x = ;
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 
int a = ;
int x = ;
// 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 的可能性。

0