c++ - C / C++如何检测整数溢出?

  显示原文与译文双语对照的内容

我正在用 C++ 编写一个程序来寻找的所有解决方案 b = c,, b c 一起使用所有位数 0 -9到底一次。 程序循环的价值观 b, 每次跑digit-counting常规, 和 b b 检查数字条件是否满足。

然而,当的时候,可以产生虚假的解决方案 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++ 访问。

时间:

方式来确定是否有操作可能会溢出,使用的位置 most-significant one-bits操作数和基本binary-math知识。

另外,任何两个操作数都会导致( 至多) 一个大于最大操作数one-bit的最大值。 例如:


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的结果的最大大小,如下所示:


bool exponentiation_is_safe(uint32_t a, uint32_t b) {
 size_t a_bits=highestOneBitPosition(a);
 return (a_bits*b<=32);
}

( 当然,替换目标整数的位数。)

我不确定在一个数字中确定最高one-bit的位置的最快方法,这里是一个brute-force方法:


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

这并不完美,但这将给你一个好主意,无论两个数字是否可以在你执行操作之前溢出。 我不知道这是否比简单地检查结果来得快,因为在 highestOneBitPosition 函数中循环,但它可能会( 尤其如果你知道操作数中有多少位) 。

我看到你正在使用无符号整数。 根据定义,用c ( 不了解 C++ ), 无符号算术不溢出。 所以,至少对于C 来说,你的观点是不对的:)

有了有符号整数之后,一旦溢出,未定义行为就会发生,你的程序可以执行任何操作( 例如: 渲染测试不确定) 。


#include <limits.h>
int a = <something>;
int x = <something>;
a += x;/* UB */
if (a <0) {/* unreliable test */
/*.. . */
}

创建一个符合项目需要测试之前溢出生成表示溢出。 方法也可以与无符号整数一起使用


#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 */;
/*.. . same thing for subtraction, multiplication, and division */

一些编译器提供对CPU中整数溢出标志的访问,然后可以测试,但这不是标准的。

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


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

警告:使用 -O2 编译时,GCC可以优化溢出检查。 选项 -Wall 将在某些情况下给出警告,比如


if (a + b <a) {/* deal with overflow */}

但在本例中不存在:


b = abs(a);
if (b <0) {/* deal with overflow */}

惟一安全的方法是在出现溢出之前检查溢出,如证书页中描述的那样,这将是非常乏味的使用系统的方法。

-fwrapv 编译解决了问题,但禁用了一些优化。

我们急需一个更好的解决方案。 我认为编译器在进行优化时应该默认发出一个依赖溢出的优化。 当前情况允许编译器优化溢出检查,这在我看来是不可接受的。

最简单的方法是将 unsigned long 转换为 unsigned long long,进行乘法,并将结果与 0 x100000000LL比较。

你可能会发现,这是更有效的比做部门作为你所做的例子。

哦,而且它可以在 C++ 和( 你已经用两种方法标记了问题) 中工作。


刚看了一下 glibc手册 。 这里提到了一个整数溢出陷阱( FPE_INTOVF_TRAP ) 作为 SIGFPE的一部分。 除了手册中讨厌的部分,这将是理想的:

FPE_INTOVF_TRAP 整数溢出( 不可能在hardware-specific程序中使用,除非你在中启用溢出补漏白) 。

真是有点羞愧。

对于无符号整数,只需检查结果是否小于以下参数之一:


unsigned int r, a, b;
r = a+b;
if (r <a)
{
//overflow
}

对于有符号整数,你可以检查参数和结果的符号。 不同符号的整数不能溢出,相同符号的整数溢出的结果是不同的符号:


signed int r, a, b, s;
r = a+b;
s = a>=0;
if (s == (b>=0) && s!= (r>=0))
{
//overflow
}

Clang 3.4和上,以及 GCC 5和上,提供已经检查的算术生成。 它们为这个问题提供了一个非常快速的解决方案,尤其在与bit-testing安全检查相比。

对于有关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 是否包含溢出的结果。 我认为结果是未定义的( 可能是溢出的结果) 。

每个算术操作都有一个 __builtin,可以溢出( 加法,减法,乘法),带有符号和无符号变量,以及正常大小和长长度。 名称的语法为 __builtin_[us](operation)(l?l?)_overflow :

  • u unsigned或 s 签署;
  • 操作是 addsub 或者 mul 之一;
  • 没有 l 后缀表示操作数是 int ;一个 l 表示 long ;两个 llong long

因此,对于选中的有符号长整数加法,它将是 __builtin_saddl_overflow 。 完整列表可以在 Clang文档页面中找到。

GCC 5和更高版本提供了一般的构建,而不指定变量的类型: __builtin_add_overflow__builtin_sub_overflow__builtin_mul_overflow

构建到平台最适合的平台。 在x86上,他们检查溢出和签名标志。

工作室的视觉 cl.exe 没有任何等价的,尽管你将能够构建与叮当声从 VS2015 Windows 项目。 如果这是你的选择,你可以为选中的算法生成小的包装函数,并使用cl构建其余部分,如往常一样。

clang现在支持有符号整数和无符号整数的动态溢出检查。 查看 -fsanitize=integer web switch 。 目前它只是一个 C++ 编译器,为调试目的提供了完全支持的动态溢出检查。

我看到很多人回答过关于溢出的问题,但我想解决他原来的问题。 他说问题是要找到一个 b =c使所有数字都不重复使用。 这不是他在这篇文章中提到的,但我仍然认为有必要研究问题的上限,并得出结论,他永远都不需要计算或者检测溢出( 注意: 我不擅长数学,所以我一步一步来,但最终结果是这么简单,这可能有一个简单的公式。

主要的一点是,问题所需要的上限,例如或者c 是。 总之,从简单和非琐碎部分分割问题:

  • x 0 == 1 ( 9,8,7,6,5,4,3,的所有排列)
  • x 1 == x ( 不可能有解决方案)
  • 0 b == 0 ( 不可能有解决方案)
  • 1 b == 1 ( 不可能有解决方案)
  • a b ,> 1,> 1 ( 非琐碎)

现在我们只需要证明没有其他的解决方案是可行的,并且只有排列是有效的( 然后打印它们的代码很简单) 。 我们回到上限。 实际上上限是c ≤ 98.765.432. 它是上限,因为它是带 8位( 每一个和b 个数字总共为 10个数字)的最大数字。 这个上限只是对于c,因为a和b的界限必须要低得多,因为指数增长,我们可以计算出,不同b 2上限:


 9938.08^2 == 98765432
 462.241^3 == 98765432
 99.6899^4 == 98765432
 39.7119^5 == 98765432
 21.4998^6 == 98765432
 13.8703^7 == 98765432
 9.98448^8 == 98765432
 7.73196^9 == 98765432
 6.30174^10 == 98765432
 5.33068^11 == 98765432
 4.63679^12 == 98765432
 4.12069^13 == 98765432
 3.72429^14 == 98765432
 3.41172^15 == 98765432
 3.15982^16 == 98765432
 2.95305^17 == 98765432
 2.78064^18 == 98765432
 2.63493^19 == 98765432
 2.51033^20 == 98765432
 2.40268^21 == 98765432
 2.30883^22 == 98765432
 2.22634^23 == 98765432
 2.15332^24 == 98765432
 2.08826^25 == 98765432
 2.02995^26 == 98765432
 1.97741^27 == 98765432

注意,例如最后一行: 它表示 1.97 ^27 ~98M. 例如 1 ^27 == 1和 2 == 134.217.728,这不是一个解决方案,因为它有 9位的( 2> 1.97,所以它实际上比应该测试的要大) 。 可以看出,用于测试和的组合非常小。 对于 == 14,我们需要尝试 2和 3 。 对于 == 3,我们从 2开始,在 462处停止。 所有结果都被授予小于 ~98M.

现在只测试上面的所有组合,查找那些不重复任何数字的组合:


 ['0', '2', '4', '5', '6', '7', '8'] 2^84 = 7056
 ['1', '2', '3', '4', '5', '8', '9'] 2^59 = 3481
 ['0', '1', '2', '3', '4', '5', '8', '9'] 2^59 = 3481 (+leading zero)
 ['1', '2', '3', '5', '8'] 3^8 = 512
 ['0', '1', '2', '3', '5', '8'] 3^8 = 512 (+leading zero)
 ['1', '2', '4', '6'] 2^4 = 16
 ['0', '1', '2', '4', '6'] 2^4 = 16 (+leading zero)
 ['1', '2', '4', '6'] 4^2 = 16
 ['0', '1', '2', '4', '6'] 4^2 = 16 (+leading zero)
 ['1', '2', '8', '9'] 2^9 = 81
 ['0', '1', '2', '8', '9'] 2^9 = 81 (+leading zero)
 ['1', '3', '4', '8'] 4^3 = 81
 ['0', '1', '3', '4', '8'] 4^3 = 81 (+leading zero)
 ['2', '3', '6', '7', '9'] 6^3 = 729
 ['0', '2', '3', '6', '7', '9'] 6^3 = 729 (+leading zero)
 ['2', '3', '8'] 3^2 = 8
 ['0', '2', '3', '8'] 3^2 = 8 (+leading zero)
 ['2', '3', '9'] 2^3 = 9
 ['0', '2', '3', '9'] 2^3 = 9 (+leading zero)
 ['2', '4', '6', '8'] 2^8 = 64
 ['0', '2', '4', '6', '8'] 2^8 = 64 (+leading zero)
 ['2', '4', '7', '9'] 2^7 = 49
 ['0', '2', '4', '7', '9'] 2^7 = 49 (+leading zero)

它们都与( 也可以通过没有'0','1的问题不匹配。 ,'9') 。

解决它的示例代码如下。 还要注意的是,是用 python 编写的,不是因为它需要任意的精度整数( 代码不计算大于 98百万的任何东西),而是因为我们发现测试量很小,所以我们需要使用高级语言来使用它的内置容器和库( 也注意: 代码有 28行) 。


 import math

 m = 98765432
 l = []
 for i in xrange(2, 98765432):
 inv = 1.0/i
 r = m**inv
 if (r <2.0): break
 top = int(math.floor(r))
 assert(top <= m)

 for j in xrange(2, top+1):
 s = str(i) + str(j) + str(j**i)
 l.append((sorted(s), i, j, j**i))
 assert(j**i <= m)

 l.sort()
 for s, i, j, ji in l:
 assert(ji <= m)
 ss = sorted(set(s))
 if s == ss:
 print '%s %d^%d = %d' % (s, i, j, ji)

 # Try with non significant zero somewhere
 s = ['0'] + s
 ss = sorted(set(s))
 if s == ss:
 print '%s %d^%d = %d (+leading zero)' % (s, i, j, ji)

如果你有一个大于你想要测试( 假设你执行 32位 添加,并且你有 64位 类型)的数据类型。 然后这将检测是否发生溢出。 我的示例是为 8 -bit添加的。 但可以放大。


uint8_t x, y;/* give these values */
const uint16_t data16 = x + y;
const bool carry = (data16> 0xff);
const bool overflow = ((~(x ^ y)) & (x ^ data16) & 0x80);

它基于本页解释的概念: http://www.cs.umd.edu/class/spring2003/cmsc311/Notes/Comb/overflow.html

对于一个 32位 示例,0xff 变成 0xffffffff0x80 变成 0x80000000,最后 uint16_t 变成 uint64_t

注意:这捕获了整数加法/减法溢出,我意识到你的问题涉及幂。 在这种情况下,除法可能是最好的方法。 这通常是 calloc 实现确保参数不会溢出以得到最终大小的一种方法。

...