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


当前回答

这取决于你用它来做什么。 执行无符号长(DWORD)加法或乘法时,最佳解决方案是使用ULARGE_INTEGER。

ULARGE_INTEGER是一个由两个dword组成的结构。全部价值 可以访问为“QuadPart”,而高DWORD访问 作为“HighPart”,低DWORD作为“LowPart”访问。

例如:

DWORD
My Addition(DWORD Value_A, DWORD Value_B)
{
    ULARGE_INTEGER a, b;

    b.LowPart = Value_A;  // A 32 bit value(up to 32 bit)
    b.HighPart = 0;
    a.LowPart = Value_B;  // A 32 bit value(up to 32 bit)
    a.HighPart = 0;

    a.QuadPart += b.QuadPart;

    // If  a.HighPart
    // Then a.HighPart contains the overflow (carry)

    return (a.LowPart + a.HighPart)

    // Any overflow is stored in a.HighPart (up to 32 bits)

其他回答

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

对于加法,任何两个操作数的结果(最多)比最大操作数的最高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函数中的循环,但它可能会(特别是如果您事先知道操作数中有多少位)。

测试溢出的简单方法是通过检查当前值是否小于前一个值来进行验证。例如,假设你有一个循环输出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溢出标志的情况下所获得的可移植性(这将需要内联汇编代码,使您的代码在实现之间无法移植)。

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

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

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(大于零的最小正数)。

从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++,你真的应该学习汇编。