在C语言中检查溢出

Question

让我们拥有

int a, b, c; // may be char or float, anything actually
c = a + b;

让int类型表示为4个字节。假设a+b所需的位数比4个字节多1位（即，假设结果是1 00 ... 0（32个二进制零））。这将导致C = 0，并且我相信计算机的微处理器会设置某种溢出标志。在C中有任何内置方法可以检查这一点吗？

实际上，我正在构建一个长度为1024位的数字类型（例如，int是一个长度为32位的内置数字类型）。我尝试使用具有128个元素的unsigned char类型数组来完成此操作。我还需要定义这些数字的加法和减法操作。我已经编写了加法代码，但我在减法方面遇到了问题。我不需要担心获得负结果，因为我调用减法函数的方式始终确保减法的结果始终为正值，但是要实现减法函数，我需要以某种方式获取被减数的二进制补码，它本身是我的自定义1024位数字。

如果我的描述难以理解，我很抱歉。如果需要，我可以进一步说明。我包括了我的添加功能和不完整的减法功能的代码。 NUM_OF_WORDS是一个常量声明为

#define NUM_OF_WORDS 128

如果您没有理解我的问题或代码的任何部分，请告诉我。

附注：我不知道如何在这个论坛上上传附件，所以我会引导您到另一个网站。我的代码可以在那里找到。

点击此页面上的下载

顺便说一句，我发现this 我打算将INT_MAX替换为UCHAR_MAX，因为我的1024位数字由char类型（8位变量）数组组成 这个检查对所有情况是否足够？

更新：

是的，我正在研究密码学。 我需要实现一个用于1024位大小整数的蒙哥马利乘法例程。 我也考虑使用GMP库，但找不到如何使用它的方法。 我查看了一个教程，在进行了一些小修改后，我能够在VC++6中构建GMP项目文件，产生了很多.obj文件，但现在我不确定该怎么做。 如果我能编写自己的数据类型，那就太好了，因为这将使我完全控制自定义数据类型上的算术运算方式，我还需要能够将其从1024位扩展到更大的数字。

- user13267

---

除非您正在进行编程练习（这确实是一个不错的练习），否则您应该考虑使用一个用于处理任意大小整数的库，例如GNU多精度算术库。 - Aasmund Eldhuset

@Kevin：我曾经遇到组合问题，导致数字超过了10^40 > 2^128。（具体来说，我正在使用一种模糊语法进行解析，我的讲师评论说这只是一个“玩具语法”。） - Fred Foo

@Kevin：此外，加密通常涉及至少该大小的整数。 - Aasmund Eldhuset

@Kevin：有很多问题与宇宙的大小无关，实际上大部分问题都是如此；-) - Steve Jessop

是的，我正在从事密码学方面的工作。 我需要实现一个用于1024位大小整数的蒙哥马利乘法例程。 - user13267

Answer 1

如果您正在添加无符号数字，则可以这样做：

c = a+b;
if (c<a) {
  // you'll get here if and only if overflow has occurred
}

你甚至可能会发现，你的编译器足够聪明，可以通过检查溢出或进位标志来实现它，而不需要进行额外的比较。例如，我刚刚将这个代码输入到gcc -O3 -S中：

unsigned int foo() {
  unsigned int x=g(), y=h();
  unsigned int z = x+y;
  return z<0 ? 0 : z;
}

并且在代码的关键部分得到了这个：

movl  $0,   %edx
addl  %ebx, %eax
cmovb %edx, %eax

你会注意到这里没有额外的比较指令。

- Gareth McCaughan

---

如果b本身是一个溢出的int，那么这种方法并不适用于所有情况。如果int的最大值为10，a = 6且b = 11，则c = 7。 - Tom Gullen

如果“int max size = 10”，那么b不能是11。显然，没有可能的代码可以告诉你，在将a和b相加时，它们中的一个是否是早期某个地方溢出的结果。 - Gareth McCaughan

请注意，尽管您所说的方法适用于无符号整数，但是这种方法不能用于有符号整数，就像OP的问题中一样。 - caf

除非我读错了，OP正在使用无符号整数，并希望能够进行减法和加法运算。与我描述的测试非常相似，可以很好地用于减法：c = a-b; if (c>a) { ... }。 - Gareth McCaughan

Answer 2

与普遍的看法相反，int溢出会导致未定义行为。这意味着一旦a + b溢出，使用该值（或进行其他任何操作）就没有意义了。在溢出情况下，机器通常会执行环绕操作，但它们也可能会崩溃。

要检查在添加两个非负整数a和b时是否会发生int溢出，可以执行以下操作：

if (INT_MAX - b < a) {
        /* int overflow when evaluating a+b */
}

这是因为如果 a + b > INT_MAX，那么 INT_MAX - b < a，但是INT_MAX - b不能溢出。

你需要特别注意当b为负数的情况，这留给读者作为练习 ;)

关于您的实际目标：1024位数字与32位数字面临完全相同的问题。选择完全不同的方法可能更有前途，例如将数字表示为数字的链接列表，使用非常大的基数B。通常，B被选择为 B = sqrt(INT_MAX)，因此数字的乘法不会使机器的int类型溢出。

这样，您可以表示任意大的数字，其中“任意”意味着“仅受可用主存储器的数量限制”。

- Philip

Answer 3

如果您正在使用无符号数字，则如果 a <= UINT_MAX，b <= UINT_MAX，并且 a + b >= UINT_MAX，那么 c = (a + b) % UINT_MAX 将始终小于 a 和 b。这是唯一可能发生的情况。

因此，您可以通过这种方式检测溢出。

int add_return_overflow(unsigned int a, unsigned int b, unsigned int* c) {
    *c = a + b;
    return *c < a && *c < b;
}

- Sylvain Defresne

Answer 4

以下是在这个主题中可能有用的信息：

1. C和C++安全编码
2. IntSafe库

- Karan

Answer 5

你可以基于 C 语言的某个特性来解决问题。根据规范，当你加上两个 unsigned ints 时，“结果值与真实结果的模 2^n 同余”（“C - A reference manual” by Harbison and Steele）。这意味着你可以使用一些简单的算术检查来检测溢出：

#include <stdio.h>

int main() {
    unsigned int a, b, c;
    char *overflow;

    a = (unsigned int)-1;
    for (b = 0; b < 3; b++) {
        c = a + b;
        overflow = (a < b) ? "yes" : "no";
        printf("%u + %u = %u, %s overflow\n", a, b, c, overflow);
    }

    return 0;
}

- odrm

Answer 6

只需对两个操作数的最高有效位进行异或运算，并得出结果。此操作的结果是溢出标志。

但这并不能告诉您结果是否正确。（即使有溢出，结果可能仍然正确）例如，3 +（-1）是2，带有溢出。

为了确定使用有符号算术时结果是否正确，您需要检查两个操作数是否具有相同的符号（即最高有效位的异或）。

- Luka Rahne

Answer 7

当你将1加到INT_MAX时，你最终会得到INT_MIN（即溢出）。 在C中，没有可靠的方法来测试溢出，因为所有32个字节都用于表示整数（而不是状态标志）。你只能测试一下你得到的数字是否在有效范围内，就像你链接中所示。

你会得到一些答案建议你可以测试if (c < a)，但请注意，你可能会将a和/或b的值溢出到超过a的数字（但仍然溢出）的程度。

- Ben Stott