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


当前回答

要以一种可移植的方式执行无符号乘法而不溢出,可以使用以下方法:

... /* begin multiplication */
unsigned multiplicand, multiplier, product, productHalf;
int zeroesMultiplicand, zeroesMultiplier;
zeroesMultiplicand = number_of_leading_zeroes( multiplicand );
zeroesMultiplier   = number_of_leading_zeroes( multiplier );
if( zeroesMultiplicand + zeroesMultiplier <= 30 ) goto overflow;
productHalf = multiplicand * ( c >> 1 );
if( (int)productHalf < 0 ) goto overflow;
product = productHalf * 2;
if( multiplier & 1 ){
   product += multiplicand;
   if( product < multiplicand ) goto overflow;
}
..../* continue code here where "product" is the correct product */
....
overflow: /* put overflow handling code here */

int number_of_leading_zeroes( unsigned value ){
   int ctZeroes;
   if( value == 0 ) return 32;
   ctZeroes = 1;
   if( ( value >> 16 ) == 0 ){ ctZeroes += 16; value = value << 16; }
   if( ( value >> 24 ) == 0 ){ ctZeroes +=  8; value = value <<  8; }
   if( ( value >> 28 ) == 0 ){ ctZeroes +=  4; value = value <<  4; }
   if( ( value >> 30 ) == 0 ){ ctZeroes +=  2; value = value <<  2; }
   ctZeroes -= x >> 31;
   return ctZeroes;
}

其他回答

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

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

查看info as和info 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位无符号整数仍然可以正常工作。基本上,我创建了一个掩码,它将屏蔽除最重要的位外的所有内容。然后,对两个整数进行掩码,如果其中任何一个没有设置该位,则加法是安全的。

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

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

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

要以一种可移植的方式执行无符号乘法而不溢出,可以使用以下方法:

... /* begin multiplication */
unsigned multiplicand, multiplier, product, productHalf;
int zeroesMultiplicand, zeroesMultiplier;
zeroesMultiplicand = number_of_leading_zeroes( multiplicand );
zeroesMultiplier   = number_of_leading_zeroes( multiplier );
if( zeroesMultiplicand + zeroesMultiplier <= 30 ) goto overflow;
productHalf = multiplicand * ( c >> 1 );
if( (int)productHalf < 0 ) goto overflow;
product = productHalf * 2;
if( multiplier & 1 ){
   product += multiplicand;
   if( product < multiplicand ) goto overflow;
}
..../* continue code here where "product" is the correct product */
....
overflow: /* put overflow handling code here */

int number_of_leading_zeroes( unsigned value ){
   int ctZeroes;
   if( value == 0 ) return 32;
   ctZeroes = 1;
   if( ( value >> 16 ) == 0 ){ ctZeroes += 16; value = value << 16; }
   if( ( value >> 24 ) == 0 ){ ctZeroes +=  8; value = value <<  8; }
   if( ( value >> 28 ) == 0 ){ ctZeroes +=  4; value = value <<  4; }
   if( ( value >> 30 ) == 0 ){ ctZeroes +=  2; value = value <<  2; }
   ctZeroes -= x >> 31;
   return ctZeroes;
}

警告:GCC在使用-O2编译时会优化掉溢出检查。 选项-Wall会在某些情况下给你一个警告

if (a + b < a) { /* Deal with overflow */ }

但在这个例子中不是:

b = abs(a);
if (b < 0) { /* Deal with overflow */ }

唯一安全的方法是在溢出发生之前检查溢出,正如CERT论文中所描述的那样,系统地使用这种方法将非常繁琐。

使用-fwrapv编译可以解决这个问题,但会禁用一些优化。

我们迫切需要一个更好的解决方案。我认为编译器应该发出一个警告,默认情况下,优化依赖于溢出没有发生。目前的情况允许编译器优化掉溢出检查,这在我看来是不可接受的。