如何检测无符号整数乘法溢出？

Question

如何检测无符号整数乘法溢出？我在C ++编写一个程序来找到所有的解决方案一b = c ^，其中一个，b和c ^一起使用所有的数字0-9只出现一次。该方案在循环值一和b，这一个数字计数例行每次跑了一个，b和一个b以检查是否数字的条件感到满意。然而，当可以产生伪解一个b溢出整数限制。我最终使用以下代码检查：unsigned long b, c, c_test;...c_test=c*b;          // Possible overflowif (c_test/b != c) {/* There has been an overflow*/}else c=c_test;      // No overflow有没有更好的方法来测试溢出？我知道有些芯片有一个内部标志，当溢出发生时会设置，但我从未见过通过C或C ++访问它。请注意，在C和C ++中，签名 int溢出是未定义的行为，因此您必须在不实际导致它的情况下检测它。有关添加前的signed int overflow，请参阅在C / C ++中检测带符号的溢出。

Answer 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);}

（当然，替换目标整数的位数。）

我不确定以最快的方式确定数字中最高的一位的位置，这是一种强力方法：

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

它并不完美，但是在你进行操作之前，这会让你知道任何两个数字是否会溢出。我不知道它是否比简单地以你建议的方式检查结果更快，因为highestOneBitPosition函数中的循环，但它可能（特别是如果你事先知道操作数中有多少位）。

Answer 2

Clang 3.4+和GCC 5+提供经过检查的算术内置函数。它们为这个问题提供了一个非常快速的解决方案，特别是与比特测试安全检查相比。

对于OP问题中的示例，它可以这样工作：

unsigned long b, c, c_test;if (__builtin_umull_overflow(b, c, &c_test)){
    // returned non-zero: there has been an overflow}else{
    // return zero: there hasn't been an overflow}

c_test如果发生溢出，Clang文档没有指定是否包含溢出的结果，但GCC文档说它确实存在溢出。鉴于这两者似乎是__builtin兼容的，可以安全地假设这也是Clang的工作方式。

__builtin对于int大小，长大小和长long大小，每个算术运算都有一个可以溢出（加法，减法，乘法），带有符号和无符号变量。该名称的语法是__builtin_[us](operation)(l?l?)_overflow：

• u对于未签名或s对签名的 ;

• 操作是其中之一add，sub或mul;

• 没有l后缀意味着操作数是ints; 一个l手段long; 两个l意思是long long。

因此，对于已检查的带符号长整数，它将是__builtin_saddl_overflow。完整列表可以在Clang文档页面上找到。

GCC 5+和锵3.8+另外提供，如果没有指定值的类型工作的通用内建的：__builtin_add_overflow，__builtin_sub_overflow和__builtin_mul_overflow。这些也适用于小于的类型int。

内置程序降低到平台最佳状态。在x86上，它们检查进位，溢出和符号标志。

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

Answer 3

有些编译器可以访问CPU中的整数溢出标志，然后可以测试，但这不是标准的。

您还可以在执行乘法之前测试溢出的可能性：

if ( b > ULONG_MAX / a ) // a * b would overflow