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

一尘不染

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

我在C ++编写一个程序来找到所有的解决方案一b = c ^，其中一个，b和c ^一起使用所有的数字0-9只出现一次。该程序循环了a和b的值，并且每次在a，b和a b上运行一个数字计数例程，以检查是否满足数字条件。

但是，当a b超出整数限制时，可能会生成伪解。我最终使用如下代码检查了这一点：

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 ++访问它。

请注意，在C和C ++中，签名 int溢出是未定义的行为，因此您必须在没有实际引起它的情况下对其进行检测。

阅读 839

2020-09-22

共1个答案

一尘不染

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
}

Clang文档没有指定c_test如果发生溢出是否包含溢出结果，但是GCC文档说确实包含。鉴于这两个都喜欢__builtin兼容，因此可以安全地假设这也是Clang的工作方式。

有一个__builtin对每个运算，可以溢出（加法，减法，乘法），用符号和无符号的变体，对于int尺寸，长尺寸，以及长长的大小。名称的语法为__builtin_[us](operation)(l?l?)_overflow：

u对于未签名或s对签名的 ;
操作中的一个add，sub或mul;
没有l后缀表示操作数是ints；一种l手段long; 2 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没有直接等效项。对于无符号的加法和减法，包括将允许您使用`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是输入上的进位/借位标志，返回值是输出上的进位/借位。它似乎没有等效的有符号运算或乘法。

否则，适用于Windows的Clang现在可以投入生产了（对于Chrome来说已经足够了），因此也可以选择。

2020-09-22