如何检测无符号整数溢出?

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

当前回答

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

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

2008-10-13 23:44:49

其他回答

不能从C/ c++中访问溢出标志。

我不同意这种说法。您可以编写一些内联汇编语言并使用jo(跳转溢出)指令，假设您在x86上捕获溢出。当然，您的代码将不再能够移植到其他体系结构。

查看info as和info gcc。

2008-10-13 23:25:45

这取决于你用它来做什么。执行无符号长(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)

2013-10-03 23:43:50

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

2010-05-01 19:01:54

一种简单的方法是重写所有操作符(特别是+和*)，并在执行操作之前检查是否有溢出。

2008-10-13 23:07:19