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


当前回答

从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来说已经足够好了),所以这也是一个选择。

其他回答

有一种方法可以确定一个操作是否可能溢出,使用操作数中最高位的位置和一些基本的二进制数学知识。

对于加法,任何两个操作数的结果(最多)比最大操作数的最高1位多1位。例如:

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

对于乘法,任何两个操作数的结果(最多)是操作数的位数之和。例如:

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

类似地,你可以像这样估计a的b次方结果的最大大小:

bool exponentiation_is_safe(uint32_t a, uint32_t b) {
    size_t a_bits=highestOneBitPosition(a);
    return (a_bits*b<=32);
}

(当然,用比特数代替目标整数。)

我不确定确定数字中最高的1位位置的最快方法,这里有一个蛮力方法:

size_t highestOneBitPosition(uint32_t a) {
    size_t bits=0;
    while (a!=0) {
        ++bits;
        a>>=1;
    };
    return bits;
}

它不是完美的,但它能让你在做运算之前知道是否有两个数会溢出。我不知道它是否会比您建议的方式检查结果更快,因为highestOneBitPosition函数中的循环,但它可能会(特别是如果您事先知道操作数中有多少位)。

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

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
}

我看到你用的是无符号整数。根据定义,在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。

Clang现在支持有符号整数和无符号整数的动态溢出检查。参见-fsanitize=integer开关。目前,它是唯一完全支持用于调试目的的动态溢出检查的c++编译器。

测试溢出的简单方法是通过检查当前值是否小于前一个值来进行验证。例如,假设你有一个循环输出2的幂:

long lng;
int n;
for (n = 0; n < 34; ++n)
{
   lng = pow (2, n);
   printf ("%li\n", lng);
}

添加溢出检查的方式,我描述的结果如下:

long signed lng, lng_prev = 0;
int n;
for (n = 0; n < 34; ++n)
{
    lng = pow (2, n);
    if (lng <= lng_prev)
    {
        printf ("Overflow: %i\n", n);
        /* Do whatever you do in the event of overflow.  */
    }
    printf ("%li\n", lng);
    lng_prev = lng;
}

它既适用于无符号值,也适用于正负符号值。

当然,如果您想对递减值而不是递增值执行类似的操作,您可以将<=符号翻转,使其为>=,假设下溢的行为与溢出的行为相同。坦率地说,这是在不访问CPU溢出标志的情况下所获得的可移植性(这将需要内联汇编代码,使您的代码在实现之间无法移植)。