C语言中的二进制补码加法溢出问题

Question

我看到一段有缺陷的C代码，用于检查加法是否会溢出。对于char类型的参数，它可以正常工作，但是当参数为int类型时，它给出了错误的答案，我无法弄清楚为什么。
下面是使用short类型参数的代码。

short add_ok( short x, short y ){
    short sum = x+y;
    return (sum-x==y) && (sum-y==x);
}

这个版本在使用原始参数时没有问题，但是当你将参数更改为int（你可以使用INT_MAX来检查）时会出现问题。
你能看出这里有什么问题吗？

- Rsh

---

一个正确的检查应该是类似于 SHRT_MAX - x <= y 或者类似的东西。 - Kerrek SB

您可以在此处找到确保有符号整数操作不会导致溢出的最佳方法。 - Joseph Elcid

你能告诉我在你的机器上选择了哪些实验值以及short和int大小，以及得到了什么返回值吗？原因是因为它“在我的机器上运行正常”。 - Ghasan غسان

对于 int，您可以将两个参数都设置为 INT_MAX 进行检查。 对于 char，正如 @R.. 所说，它不会溢出。 - Rsh

Answer 1

因为在二进制补码中，整数可以按照模运算的方式排列成一个圆圈（参见模算术）。加上y然后再减去y总是会让你回到起点（未定义的行为除外）。

- Oliver Charlesworth

---

@kerrek：不确定有更好的方法用一句话来描述它！ - Oliver Charlesworth

@OliCharlesworth：环绕？ - Mike Kwan

@OliCharlesworth：也许是“环”。 - Kerrek SB

不，通常不会出现未定义行为（UB），算术运算会像R..所说的那样以int类型进行。 - Jens Gustedt

所以，它就像是跟踪并替换sum-x为(x+y)-x，对吧？ - Rsh

Answer 2

您的代码中，只有当int与short大小相同时，加法才不会溢出。x+y由于默认提升，会对x和y提升为int后进行计算，然后以实现定义的方式截断结果为short。

为什么不简单地这样做：return x+y<=SHRT_MAX && x+y>=SHRT_MIN;

- R.. GitHub STOP HELPING ICE

---

谢谢你分享这个关于类型提升的有趣事实。我之前并不知道！C语言真是一个棘手的语言。 - argentage

@airza 建议你读一本关于 C 语言的好书，最好是开始阅读 C 标准。学习掌握自己工具的运作方式从未为时过晚，同时也会带来好处。 - Alexey Frunze

Answer 3

在C编程语言中，有符号整数转换为更小的有符号整数（例如 char 类型）时，其行为是由实现定义的。尽管许多系统和程序员假设可以进行环绕溢出，但这不是一种标准行为。那么什么是环绕溢出呢？

在二进制补码表示法中，环绕溢出会发生在一个值无法用当前类型来表示时，它会在最高或最低可表示数字之间循环。这是什么意思？看看下面的例子。

在 signed char 中，可以表示的最大值为 127，最小值为 -128。当我们执行 "char i = 128" 时，存储在 i 中的值变成了 -128。因为该值比有符号整数类型要大，所以它绕过了最小值，并且如果是 "char i = 129"，则 i 将包含 -127。你看到了吗？每当一个端点达到其最大值时，它就会绕到另一端（符号）。反之亦然，如果 "char i = -129"，则 i 将包含 127，如果是 "char i = -130"，则将包含 126，因为它达到了最大值并绕过了最高值。

（最高）127、126、125、...、-126、-127、-128（最低）

如果值非常大，它将一直绕过，直到达到其范围内可以表示的值。

更新：与 char 和 short 不同，“int” 无法起作用的原因是当两个数字相加时，存在溢出的可能性（不管是 int、short 还是 char，同时不要忘记整体提升），但因为“short”和“char”的大小比“int”小，并且因为它们在表达式中被提升为“int”，所以它们会再次表示而不截断。

return (sum-x==y) && (sum-y==x);

任何溢出都会被检测到，如下面详细解释，但是当使用int时，它不会提升为任何类型，因此会发生溢出。例如，如果我执行INT_MAX+1，则结果为INT_MIN，如果我通过INT_MIN-1 == INT_MAX测试溢出，则结果为TRUE！这是因为"short"和char会被提升为int进行评估，然后被截断（溢出）。但是，int首先会发生溢出，然后再进行评估，因为它们没有被提升为更大的大小。

想象一下没有提升的char类型，并尝试使用上面的说明制造溢出并检查它们。您会发现添加或减去导致溢出的值会将您带回原来的位置。然而，在C中并非如此，因为char和"short"被提升为int，因此检测到了溢出，在int中则不是这样，因为它没有被提升为更大的大小。

更新结束

对于您的问题，我在MinGW和Ubuntu 12.04中检查了您的代码，似乎正常工作。后来我发现，该代码实际上适用于短小于int的系统，并且值未超过int范围。该行：

return (sum-x==y) && (sum-y==x);

是正确的，因为"sum-x"和"y"被评估为(int)，所以在这里没有发生上溢，而在前一行(赋值时)发生了：

short sum = x+y;

这里是一个测试。如果我在第一个输入32767，在第二个输入2，那么当：

short sum = x+y;

由于数据溢出，变量sum将包含-32767。但是当：

return (sum-x==y) && (sum-y==x);

"sum-x"（-32767 - 32767）只有在发生环绕时才会等于y（2）（然后出现错误），但由于整数提升，它从未以这种方式发生，因此"sum-x"的值变为-65534，而不等于y，这导致正确的检测。

这是我使用的代码：

#include <stdio.h>

short add_ok( short x, short y ){
    short sum = x+y;
    return (sum-x==y) && (sum-y==x);
}

int main(void) {

    short i, ii;
    scanf("%hd %hd", &i, &ii);
    getchar();

    printf("%hd", add_ok(i, ii));

    return 0;
}

请查看这里和这里。

您需要提供您正在使用的架构以及测试的实验值，因为并非每个人都会遇到您所说的问题，并且由于问题的实现定义性质。

参考资料：C99 6.3.1.3 这里，GNU C手册这里。

- Ghasan غسان

---

我稍微修改了问题，你可能需要再次检查。 - Rsh

@ArashThr，请尝试思考一下。我已经更新了它，真的无话可说 xD - Ghasan غسان

Answer 4

编译器可能会将对此表达式的所有调用都替换为1，因为它在每种情况下都是真实的。优化程序将针对sum执行复制传播操作并进行优化处理。

return (y==y) && (x==x);

然后：

return 1

这在任何情况下都是正确的，因为有符号整数溢出是未定义行为- 因此，编译器可以自由地保证 x+y-y == x 和 y+x-x == y。

如果这是一个无符号操作，它也会类似地失败- 因为溢出只是作为模运算执行，所以很容易证明

x+y mod SHRT_MAX - y mod SHRT_MAX == x

同样地，反向情况也是如此。

- argentage

---

那么你的意思是“优化器”将sum+x中的sum替换为x+y？另外，你所说的“未定义行为”是什么意思？ - Rsh

@ArashThr 未定义行为是指标准没有对其施加任何限制的行为。实现/编译器可以随意执行任何操作。它可以拒绝编译，生成代码格式化硬盘，或创建工作方式如您所期望的代码 - 除非你在星期五运行它，否则它将格式化您的硬盘。 - Daniel Fischer

本质上，编译器会假设您的代码不会产生未定义的行为并进行适当的优化。如果确实发生了这种情况（例如，如果您的整数溢出），则您不能再保证程序中的任何内容。在实践中，结果有时可能还算可以接受-这并不意味着您应该依赖未定义的行为，而是它的存在可能使一些 C 缺陷非常难以察觉。就像这个例子。 - argentage

你能提供关于这个“优化例程”的参考资料吗？ - Rsh