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


当前回答

x86指令集包括一个无符号乘法指令,它将结果存储到两个寄存器中。要使用C中的指令,可以在64位程序(GCC)中编写以下代码:

unsigned long checked_imul(unsigned long a, unsigned long b) {
  unsigned __int128 res = (unsigned __int128)a * b;
  if ((unsigned long)(res >> 64))
    printf("overflow in integer multiply");
  return (unsigned long)res;
}

对于32位程序,需要使结果为64位,参数为32位。

另一种方法是使用依赖于编译器的intrinsic来检查标志寄存器。关于溢出的GCC文档可以从6.56内置函数执行溢出检查算术中找到。

其他回答

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

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

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

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

#include <stdio.h>
#include <stdlib.h>

#define MAX 100 

int mltovf(int a, int b)
{
    if (a && b) return abs(a) > MAX/abs(b);
    else return 0;
}

main()
{
    int a, b;

    for (a = 0; a <= MAX; a++)
        for (b = 0; b < MAX; b++) {

        if (mltovf(a, b) != (a*b > MAX)) 
            printf("Bad calculation: a: %d b: %d\n", a, b);

    }
}