小编典典

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

c

我在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溢出是未定义的行为,因此您必须在没有实际引起它的情况下对其进行检测。


阅读 129

收藏
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 Studiocl.exe没有直接等效项。对于无符号的加法和减法,包括将允许您使用`addcarry_uNNsubborrow_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