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

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&nbsp;addition_is_safe(uint32_t&nbsp;a,&nbsp;uint32_t&nbsp;b)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;size_t&nbsp;a_bits=highestOneBitPosition(a),&nbsp;b_bits=highestOneBitPosition(b); &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;(a_bits<32&nbsp;&&&nbsp;b_bits<32);}对于乘法，任何两个操作数将导致（最多）操作数的位总和。例如：bool&nbsp;multiplication_is_safe(uint32_t&nbsp;a,&nbsp;uint32_t&nbsp;b)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;size_t&nbsp;a_bits=highestOneBitPosition(a),&nbsp;b_bits=highestOneBitPosition(b); &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;(a_bits+b_bits<=32);}同样，您可以估算结果的最大大小a，b如下所示：bool&nbsp;exponentiation_is_safe(uint32_t&nbsp;a,&nbsp;uint32_t&nbsp;b)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;size_t&nbsp;a_bits=highestOneBitPosition(a); &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;(a_bits*b<=32);}（当然，替换目标整数的位数。）我不确定以最快的方式确定数字中最高的一位的位置，这是一种强力方法：size_t&nbsp;highestOneBitPosition(uint32_t&nbsp;a)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;size_t&nbsp;bits=0; &nbsp;&nbsp;&nbsp;&nbsp;while&nbsp;(a!=0)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;++bits; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a>>=1; &nbsp;&nbsp;&nbsp;&nbsp;}; &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;bits;}它并不完美，但是在你进行操作之前，这会让你知道任何两个数字是否会溢出。我不知道它是否比简单地以你建议的方式检查结果更快，因为highestOneBitPosition函数中的循环，但它可能（特别是如果你事先知道操作数中有多少位）。

Answer 2

Clang 3.4+和GCC 5+提供经过检查的算术内置函数。它们为这个问题提供了一个非常快速的解决方案，特别是与比特测试安全检查相比。对于OP问题中的示例，它可以这样工作：unsigned&nbsp;long&nbsp;b,&nbsp;c,&nbsp;c_test;if&nbsp;(__builtin_umull_overflow(b,&nbsp;c,&nbsp;&c_test)){ &nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;returned&nbsp;non-zero:&nbsp;there&nbsp;has&nbsp;been&nbsp;an&nbsp;overflow}else{ &nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;return&nbsp;zero:&nbsp;there&nbsp;hasn't&nbsp;been&nbsp;an&nbsp;overflow}c_test如果发生溢出，Clang文档没有指定是否包含溢出的结果，但GCC文档说它确实存在溢出。鉴于这两者似乎是__builtin兼容的，可以安全地假设这也是Clang的工作方式。__builtin对于int大小，长大小和长long大小，每个算术运算都有一个可以溢出（加法，减法，乘法），带有符号和无符号变量。该名称的语法是__builtin_[us](operation)(l?l?)_overflow：u对于未签名或s对签名的&nbsp;;操作是其中之一add，sub或mul;没有l后缀意味着操作数是ints;&nbsp;一个l手段long;&nbsp;两个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&nbsp;char&nbsp;_addcarry_u32(unsigned&nbsp;char&nbsp;c_in,&nbsp;unsigned&nbsp;int&nbsp;src1,&nbsp;unsigned&nbsp;int&nbsp;src2,&nbsp;unsigned&nbsp;int&nbsp;*sum); unsigned&nbsp;char&nbsp;_subborrow_u32(unsigned&nbsp;char&nbsp;b_in,&nbsp;unsigned&nbsp;int&nbsp;src1,&nbsp;unsigned&nbsp;int&nbsp;src2,&nbsp;unsigned&nbsp;int&nbsp;*diff);c_in/&nbsp;b_in是输入的进位/借位标志，返回值是输出的进位/借位。它似乎没有签名操作或乘法的等价物。否则，Clang for Windows现在可以投入生产（对Chrome来说已经足够了），所以这也是一个选择。

Answer 3

有些编译器可以访问CPU中的整数溢出标志，然后可以测试，但这不是标准的。您还可以在执行乘法之前测试溢出的可能性：if&nbsp;(&nbsp;b&nbsp;>&nbsp;ULONG_MAX&nbsp;/&nbsp;a&nbsp;)&nbsp;//&nbsp;a&nbsp;*&nbsp;b&nbsp;would&nbsp;overflow