在C / C ++中检测签名溢出
乍一看，这个问题可能看起来像是如何检测整数溢出重复？ 但是它实际上是显着不同的。
我发现虽然检测到一个无符号的整数溢出非常微不足道，但是在C / C ++中检测一个有符号的溢出实际上比大多数人想象的要困难。
最明显而又天真的做法是这样的：
int add(int lhs, int rhs) { int sum = lhs + rhs; if ((lhs >= 0 && sum < rhs) || (lhs < 0 && sum > rhs)) { /* an overflow has occurred */ abort(); } return sum; } 这个问题是根据C标准，有符号整数溢出是未定义的行为。 换句话说，根据这个标准，只要你甚至导致了一个签名溢出，你的程序就像你解引用一个空指针一样无效。 所以你不能导致未定义的行为，然后尝试检测事实后的溢出，就像在上面的post-condition检查的例子中一样。
即使上面的检查可能在许多编译器上工作，你也不能指望它。 事实上，因为C标准说未定义有符号整数溢出，所以有些编译器（比如GCC）会在优化标志被设置的时候优化掉上面的检查 ，因为编译器假定一个签名溢出是不可能的。 这完全打破了检查溢出的企图。
所以，另一种检查溢出的方法是：
int add(int lhs, int rhs) { if (lhs >= 0 && rhs >= 0) { if (INT_MAX - lhs <= rhs) { /* overflow has occurred */ abort(); } } else if (lhs < 0 && rhs < 0) { if (lhs <= INT_MIN - rhs) { /* overflow has occurred */ abort(); } } return lhs + rhs; }
这似乎更有希望，因为我们实际上并没有把两个整数加在一起，直到我们事先确定执行这样的加法不会导致溢出。 因此，我们不会造成任何不确定的行为。
但是，不幸的是，这个解决scheme不如初始解决scheme效率低很多，因为您必须执行减法操作来testing添加操作是否可行。 即使你不关心这个（小）性能的打击，我仍然不完全相信这个解决scheme是适当的。 expression式lhs <= INT_MIN - rhs看起来与编译器可能优化的expression式类似，认为签名溢出是不可能的。
那么这里有更好的解决scheme吗？ 一些保证1）不会导致未定义的行为，2）不提供编译器优化溢出检查的机会？ 我认为可能有办法做到这一点，将两个操作数都转换为无符号数，然后通过滚动自己的二进制补码algorithm来执行检查，但是我不太确定该怎么做。
减法的方法是正确的，定义良好。 编译器不能优化它。
另一种正确的方法，如果你有一个更大的整数types可用，就是在较大的types中执行算术，然后在转换时检查结果是否适合较小的types
int sum(int a, int b) { long long c; assert(LLONG_MAX>INT_MAX); c = (long long)a + b; if (c < INT_MIN || c > INT_MAX) abort(); return c; }
一个好的编译器应该把整个加法和if语句转换成一个int大小的加法和一个单一的条件跳转溢出，而不是实际执行更大的加法。
编辑：正如斯蒂芬指出，我得到一个（不太好）的编译器，海湾合作委员会，生成理智的汇编。 它生成的代码不是非常慢，但肯定是不理想的。 如果有人知道这个代码中的变体会让gcc做正确的事情，我很乐意看到他们。
不，你的第二个代码是不正确的，但你是接近的：如果你设置
int half = INT_MAX/2; int half1 = half + 1;
加法的结果是INT_MAX 。 （ INT_MAX总是奇数）。 所以这是有效的input。 但是在你的日常工作中，你将拥有INT_MAX - half == half1 ，你会放弃。 假阳性
这个错误可以通过在两个检查中加上<而不是<=来修复。
但是，那么你的代码也不是最优的。 以下将做到：
int add(int lhs, int rhs) { if (lhs >= 0) { if (INT_MAX - lhs < rhs) { /* would overflow */ abort(); } } else { if (rhs < INT_MIN - lhs) { /* would overflow */ abort(); } } return lhs + rhs; }
要看到这是有效的，你必须在不平等的两边象征性地加上lhs ，这就给了你正确的算术条件，使你的结果超越界限。
恕我直言，处理溢出紧缩C ++代码的最东方的方法是使用SafeInt<T> 。 这是一个在代码plex上托pipe的跨平台C ++模板，它提供了您在此期望的安全保证。
我发现它使用起来非常直观，因为它提供了许多与正常数字操作相同的使用模式，并通过exception表示stream过和stream出。
如果你使用内联汇编器，你可以检查溢出标志 。 另一种可能是你可以使用safeint数据types 。 我build议阅读本文关于Integer安全 。
对于海湾合作委员会的情况，从海湾合作委员会5.0发行说明，我们可以看到它现在提供了一个__builtin_add_overflow检查溢出另外：
增加了一套新的带有溢出检查function的内置函数：__builtin_add_overflow，__builtin_sub_overflow和__builtin_mul_overflow，以及与clang以及其他变体的兼容性。 这些内build函数有两个整数参数（不需要有相同的types），参数扩展为无限精度的有符号types，对这些参数执行+， – 或*，并将结果存储在一个整型variables中由最后一个论点。 如果存储值等于无限精度结果，则内置函数返回false，否则返回true。 将保存结果的整型variables的types可能与前两个参数的types不同。
例如：
__builtin_add_overflow( rhs, lhs, &result )
我们可以从gcc文档中看到内置函数执行算术溢出检查 ：
这些内置函数对所有参数值都有完全定义的行为。
铿锵也提供了一套检查算术builtins ：
Clang提供了一组内置的实现检查algorithm的安全关键的应用程序的方式是快速和容易地在C中表示
在这种情况下，内build的将是：
__builtin_sadd_overflow( rhs, lhs, &result )
你可能有更好的运气转换为64位整数，并testing类似的条件。 例如：
#include <stdint.h> ... int64_t sum = (int64_t)lhs + (int64_t)rhs; if (sum < INT_MIN || sum > INT_MAX) { // Overflow occurred! } else { return sum; }
你可能想仔细看看签名扩展如何在这里工作，但我认为这是正确的。
怎么样：
int sum(int n1, int n2) { int result; if (n1 >= 0) { result = (n1 - INT_MAX)+n2; /* Can't overflow */ if (result > 0) return INT_MAX; else return (result + INT_MAX); } else { result = (n1 - INT_MIN)+n2; /* Can't overflow */ if (0 > result) return INT_MIN; else return (result + INT_MIN); } }
我认为这应该适用于任何合法的INT_MIN和INT_MAX （对称与否）; 所示的function片断，但如何获得其他行为应该是显而易见的）。
最快的方法是使用GCC内build：
int add(int lhs, int rhs) { int sum; if (__builtin_add_overflow(lhs, rhs, &sum)) abort(); return sum; }
在x86上，GCC把它编译成：
mov %edi, %eax add %esi, %eax jo call_abort ret call_abort: call abort
它使用处理器的内置溢出检测。
如果使用GCC内置函数不行，下一个最快的方法是在符号位上使用位操作。 此外，还会发生签名溢出：
- 两个操作数具有相同的符号
- 结果与操作数有不同的符号。
如果操作数具有相同的符号，则~(lhs ^ rhs)的符号位开启，如果结果与操作数具有不同的符号，则lhs ^ sum的符号位开启。 所以你可以用无符号forms进行加法，以避免未定义的行为，然后使用~(lhs ^ rhs) & (lhs ^ sum)的符号位：
int add(int lhs, int rhs) { unsigned sum = (unsigned) lhs + (unsigned) rhs; if ((~(lhs ^ rhs) & (lhs ^ sum)) & 0x80000000) abort(); return (int) sum; }
这编译成：
lea (%rsi,%rdi), %eax xor %edi, %esi not %esi xor %eax, %edi test %edi, %esi js call_abort ret call_abort: call abort
这比在32位机器上使用64位types（使用gcc）快很多：
push %ebx mov 12(%esp), %ecx mov 8(%esp), %eax mov %ecx, %ebx sar $31, %ebx clt add %ecx, %eax adc %ebx, %edx mov %eax, %ecx add $-2147483648, %ecx mov %edx, %ebx adc $0, %ebx cmp $0, %ebx ja call_abort pop %ebx ret call_abort: call abort
对我来说，最简单的检查就是检查操作数和结果的符号。
让我们来看一下总和：只有当两个操作数的符号相同时，溢出才会出现在两个方向，+或 – 上。 而且，显然，当结果的符号与操作数的符号不一致时，溢出将会是。
所以，这样的支票就足够了：
int a, b, sum; sum = a + b; if (((a ^ ~b) & (a ^ sum)) & 0x80000000) detect_oveflow();
编辑：如Nilsbuild议，这是正确的if条件：
((((unsigned int)a ^ ~(unsigned int)b) & ((unsigned int)a ^ (unsigned int)sum)) & 0x80000000)
而且从什么时候开始
add eax, ebx
导致未定义的行为？ 在Intel x86指令集refference中没有这样的事情。
显而易见的解决scheme是转换为无符号，以获得良好定义的无符号溢出行为：
int add(int lhs, int rhs) { int sum = (unsigned)lhs + (unsigned)rhs; if ((lhs >= 0 && sum < rhs) || (lhs < 0 && sum > rhs)) { /* an overflow has occurred */ abort(); } return sum; }
这将使用signed和unsigned之间的实现定义的超范围值转换替代未定义的signed overflow行为，所以您需要检查编译器的文档以确切地知道将会发生什么，但至less应该定义好，并且应该在任何二进制补码机器上做正确的事情，而不会在转换上产生信号，这几乎是过去20年来build立的所有机器和C编译器。
在添加两个long int值的情况下，可移植代码可以将long int值分为低int部分和高int部分（如果long int与int相同，则将long int部分划分为short部分）：
static_assert(sizeof(long) == 2*sizeof(int), ""); long a, b; int ai[2] = {int(a), int(a >> (8*sizeof(int)))}; int bi[2] = {int(b), int(b >> (8*sizeof(int))}); ... use the 'long' type to add the elements of 'ai' and 'bi'
使用内联汇编是针对特定CPU的最快方法：
long a, b; bool overflow; #ifdef __amd64__ asm ( "addq %2, %0; seto %1" : "+r" (a), "=ro" (overflow) : "ro" (b) ); #else #error "unsupported CPU" #endif if(overflow) ... // The result is stored in variable 'a'
我认为这是有效的：
int add(int lhs, int rhs) { volatile int sum = lhs + rhs; if (lhs != (sum - rhs) ) { /* overflow */ //errno = ERANGE; abort(); } return sum; }
使用volatile会使编译器不再优化，因为它认为加法和减法之间的sum可能已经改变了。
对x86_64使用gcc 4.4.3，这段代码的程序集确实执行了加法，减法和testing，尽pipe它将所有内容存储在堆栈中，并且不需要堆栈操作。 我甚至尝试过register volatile int sum =但是程序集是一样的。
对于只有int sum = （没有volatile或register）的版本，函数没有进行testing，只用一个lea指令进行加法lea （ lea是Load Load Address，常用于加法而不用触及标志寄存器）。
你的版本是更大的代码，并有更多的跳跃，但我不知道哪个会更好 。
