在 C/C++ 中检测有符号溢出

不，您的第二个代码不正确，但您很接近：如果您设置

int half = INT_MAX/2;
int half1 = half + 1;

加法的结果是 INT_MAX。 （INT_MAX 始终是奇数）。所以这是有效的输入。但在您的例程中，您将有 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，这会准确地为您提供结果超出范围的算术条件。

---

您的减法方法是正确且定义明确的。编译器无法优化它。

如果您有更大的整数类型可用，另一种正确的方法是在较大的类型中执行算术，然后在将其转换回时检查结果是否适合较小的类型

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 来生成健全的 asm 时遇到了麻烦。它生成的代码不是很慢，但肯定不是最理想的。如果有人知道此代码的变体将使 gcc 做正确的事情，我很乐意看到它们。

---

对于 gcc 案例，从 gcc 5.0 Release notes 我们可以看到它现在还提供了一个 __builtin_add_overflow 用于检查溢出：

添加了一组新的内置函数，用于具有溢出检查的算术：__builtin_add_overflow、__builtin_sub_overflow 和 __builtin_mul_overflow，并与 clang 以及其他变体兼容。这些内置函数有两个整数参数（不需要具有相同的类型），参数扩展为无限精度有符号类型，+、- 或 * 对它们执行，结果存储在指向的整数变量中通过最后一个论点。如果存储的值等于无限精度结果，则内置函数返回 false，否则返回 true。将保存结果的整数变量的类型可能与前两个参数的类型不同。

例如：

__builtin_add_overflow( rhs, lhs, &result )

我们可以从 gcc 文档 Built-in Functions to Perform Arithmetic with Overflow Checking 中看到：

[...]这些内置函数对所有参数值都有完全定义的行为。

clang 还提供了一组 checked arithmetic builtins：

Clang 提供了一组内置函数，它们以在 C 中快速且易于表达的方式为安全关键应用程序实现检查算法。

在这种情况下，内置将是：

__builtin_sadd_overflow( rhs, lhs, &result )

---

恕我直言，处理溢出敏感 C++ 代码的最简单方法是使用 SafeInt<T>。这是托管在 code plex 上的跨平台 C++ 模板，可提供您在此处所需的安全保证。

https://github.com/dcleblanc/SafeInt

我发现它使用起来非常直观，因为它提供了许多与正常数值运算相同的使用模式，并通过异常表达溢出和溢出。

---

最快的方法是使用 GCC 内置：

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 的符号位打开。因此，您可以以无符号形式进行加法以避免未定义的行为，然后使用 ~(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 位机器（使用 gcc）上转换为 64 位类型要快得多：

    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

---

如果您使用内联汇编程序，您可以检查 overflow flag。另一种可能性是您可以使用 safeint datatype。我建议在 Integer Security 上阅读这篇论文。

---

您可能会更幸运地转换为 64 位整数并测试类似的条件。例如：

#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 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;  
} 

这用实现定义的有符号和无符号之间的超出范围值的转换替换了未定义的有符号溢出行为，因此您需要检查编译器的文档以确切知道会发生什么，但它至少应该被明确定义，并且应该在任何不会在转换时引发信号的二进制补码机器上做正确的事情，这几乎是过去 20 年中构建的每台机器和 C 编译器。

---

怎么样：

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（对称与否）；功能如图所示，但如何获得其他行为应该很明显）。

---

您的根本问题是 lhs + rhs 没有做正确的事情。但是，如果您愿意假设一个二进制补码机器，我们可以解决这个问题。假设您有一个函数 to_int_modular，该函数将 unsigned 转换为 int，并且保证与从 int 到 unsigned 的转换相反，并且它在运行时优化为无。 （参见下文了解如何实现它。）

如果您使用它来修复原始尝试中的未定义行为，并重写条件以避免 lhs >= 0 和 lhs < 0 的冗余测试，那么您会得到

int add(int lhs, int rhs)
{
 int sum = to_int_modular((unsigned)lhs + rhs);
 if (lhs >= 0) {
  if (sum < rhs)
    abort();
 } else {
  if (sum > rhs)
   abort();
 }
 return sum; 
}

它的性能应该优于 current top-voted answer，因为它具有相似的结构但需要较少的算术运算。

（重新组织 if 应该没有必要，但在 tests on godbolt 中，ICC 和 MSVC 确实自行消除了冗余测试，但 GCC 和 Clang 令人惊讶地没有。）

如果您希望以更大的尺寸计算结果然后进行边界检查，那么进行边界检查的一种方法是

 long long sum = (long long)lhs + rhs;
 if ((int)sum != sum)
  abort();

...除了行为在溢出时未定义。但是您可以使用相同的辅助函数来解决这个问题：

 if (to_int_modular(sum) != sum)

在不够聪明的编译器上，这可能会优于 current accepted answer 以对其进行优化以测试溢出标志。

不幸的是，测试（对 Godbolt 的目视检查）表明 GCC、ICC 和 MSVC 使用上面的代码比使用已接受答案中的代码做得更好，但 Clang 使用已接受答案中的代码做得更好。像往常一样，没有什么是容易的。

这种方法只适用于int和unsigned的范围相当大的架构，下面的具体实现也依赖于它的二进制补码。不符合这些规格的机器非常罕见，但无论如何我都会检查它们：

static_assert(INT_MIN + INT_MAX == -1 && UINT_MAX + INT_MIN == INT_MAX);

实现 to_int_modular 的一种方法是

inline int to_int_modular(unsigned u) {
    int i;
    memcpy(&i, &u, sizeof(i));
    return i;
}

所有主要的 x64 编译器都可以毫无问题地优化它，但是当禁用优化时，MSVC 和 ICC 会生成对 memcpy 的调用，如果你经常使用这个函数，这可能会有点慢。此实现还取决于标准可能无法保证的 unsigned 和 int 表示的细节。

另一种方式是这样的：

inline int to_int_modular(unsigned u) {
    return u <= INT_MAX ? (int)u : (int)(u - INT_MIN) + INT_MIN;
}

除了 ICC，所有主要的 x64 编译器都对其进行了优化，这使得它和我能想到的每一个变体都变得一团糟。 ICX 做得很好，而且似乎英特尔正在放弃 ICC 并转向 ICX，所以也许这个问题会自行解决。

---

在添加两个 long 值的情况下，可移植代码可以将 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'

---

对我来说，最简单的检查是检查操作数和结果的符号。

让我们检查一下 sum：溢出可能发生在两个方向，+ 或 -，只有当两个操作数具有相同的符号时。而且，很明显，当结果的符号与操作数的符号不同时，就会发生溢出。

所以，这样的检查就足够了：

int a, b, sum;
sum = a + b;
if  (((a ^ ~b) & (a ^ sum)) & 0x80000000)
    detect_oveflow();

编辑：正如 Nils 所建议的，这是正确的 if 条件：

((((unsigned int)a ^ ~(unsigned int)b) & ((unsigned int)a ^ (unsigned int)sum)) & 0x80000000)

自从当指令

add eax, ebx 

导致未定义的行为？ Intel x86 指令集参考中没有这样的东西。

---

我认为这有效：

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，此代码的程序集确实执行加法、减法和测试，尽管它将所有内容存储在堆栈和不需要的堆栈操作中。我什至试过 register volatile int sum = 但程序集是一样的。

对于只有 int sum =（无 volatile 或寄存器）的版本，该函数没有进行测试，只使用一条 lea 指令进行了加法（lea 是加载有效地址，通常用于在不触及标志寄存器）。

你的版本是更大的代码并且有更多的跳转，但我不知道哪个会更好。

---