为什么无符号整数溢出是定义行为，而有符号整数溢出不是？

Question

为什么无符号整数溢出是定义行为，而有符号整数溢出不是？

c++cundefined-behaviorinteger-overflow

267

无符号整数溢出在C和C++标准中都有明确定义。例如，C99标准(§6.2.5/9)规定：

涉及无符号操作数的计算永远不会溢出，因为不能用结果类型表示的结果将对能够表示的结果类型最大值加1取模

然而，两个标准都声明有符号整数溢出是未定义的行为。同样来自C99标准 (§3.4.3/1)：

未定义行为的一个例子是整数溢出时的行为

这种差异存在历史原因或（更好的！）技术原因吗？

- anthonyvd

67

可能是因为表示有符号整数的方式不止一种。这个标准没有明确指定使用哪种方式，至少在C++中没有。 - juanchopanza

有用的链接：http://en.wikipedia.org/wiki/Signed_number_representations - Robᵩ

7

JuanchoPanza说的很有道理。据我理解，最初的C标准在很大程度上规范了现有的实践。如果当时所有的实现都同意无符号数的“溢出”应该怎么处理，那么这就是将其标准化的一个很好的理由。但是他们对于有符号数的溢出处理没有达成一致，所以这个部分没有被纳入标准中。 - user743382

2

@DavidElliman 无符号加法溢出可以轻松检测 (if (a + b < a))。有符号和无符号类型的乘法溢出都很难检测。 - user743382

5

@DavidElliman说：这不仅仅是能否检测出来的问题，更重要的是结果。在使用符号位加数表示法时，MAX_INT+1 == -0，而在二进制补码表示法中则为INT_MIN。 - David Rodríguez - dribeas

显示剩余2条评论

7个回答

19

除了Pascal的好回答（我相信这是主要动力），还有可能是一些处理器在有符号整数溢出时会引发异常，这当然会导致问题，如果编译器必须"安排另一种行为"（例如使用额外的指令来检查潜在溢出并在这种情况下进行不同的计算）。

值得注意的是，“未定义的行为”并不意味着“无法工作”。它意味着实现可以在这种情况下做任何它想做的事情。这包括做“正确的事情”以及“呼叫警方”或“崩溃”。大多数编译器在可能的情况下会选择“做正确的事情”，假设相对容易定义（在这种情况下是如此）。但是，如果您的计算中存在溢出，了解其实际结果以及编译器可能执行与预期不同的操作很重要（而这可能会因编译器版本、优化设置等而异）。

- Mats Petersson

32

编译器并不希望你依赖它们可以正确处理所有情况，事实上，大多数编译器都会在你使用优化编译 int f(int x) { return x+1>x; } 后将其优化为 return 1;，因此告诉你不能盲目依赖编译器。其中GCC和ICC是默认采用这种优化方式的。 - Pascal Cuoq

1

请参考 http://ideone.com/cki8nM，这是一个示例程序，根据优化级别在面对 int 溢出时会给出不同的结果。我认为这证明了你的回答给出了错误的建议。 - Magnus Hoff

是的，我在谈论使用具有不同整数格式的硬件，而不是二进制补码。我确信有些硬件使用的是一的补码（不常见，但确实存在于现实世界中）。我不确定是否有“仅符号位”的硬件。 - Mats Petersson

@MatsPetersson：存在为没有有符号算术概念的处理器编写的C编译器；据我所知，这些编译器无一例外地使用二进制补码数学。我不知道是否有任何平台的C编译器会禁止使用有符号算术指令，而只使用无符号算术指令进行所有数学运算，包括有符号算术；这样的代码可能不如使用本机有符号算术指令的代码快，但如果语义上需要包装二进制补码算术... - supercat

1

负值需要存在并“工作”，以使编译器正常工作。当然，在处理器中缺少有符号值时，完全可以通过使用无符号值来解决问题，无论是使用一补数还是二补数，取决于指令集的基础上哪个更合理。这通常比具有硬件支持要慢得多，但与不支持硬件浮点运算的处理器或类似处理器没有区别 - 它只是增加了大量额外的代码。 - Mats Petersson

显示剩余11条评论

12

首先，请注意，像C11 3.4.3这样的示例和脚注都不是规范文本，因此不相关且不应引用！

有关整数和浮点数溢出是未定义行为的相关文本如下：

C11 6.5/5

如果在表达式求值过程中出现异常情况（即，结果在其类型的可表示值范围之外或数学上没有定义），则其行为是未定义的。

对于无符号整数类型的行为的澄清可以在此处找到：

C11 6.2.5/9

有符号整数类型的非负值范围是相应无符号整数类型的子范围，并且在每个类型中表示相同的值。涉及无符号操作数的计算永远不会溢出，因为不能由所得无符号整数类型表示的结果将被模除比结果类型大一的数字。

这使得无符号整数类型成为特殊情况。

还要注意如果任何类型转换为有符号类型并且旧值不能再表示，则存在异常。然后行为仅由实现定义，尽管可能会引发信号。

C11 6.3.1.3

6.3.1.3 有符号和无符号整数

当整数类型的值被转换为另一种整数类型而不是_Bool时，如果该值可以由新类型表示，则它保持不变。

否则，如果新类型是无符号的，则通过反复添加或减去可以在新类型中表示的最大值加一来转换该值，直到该值在新类型的范围内。

否则，新类型为有符号，该值将被强制转换为相应类型中的等效值。无法用此表示；结果可能是实现定义的，或者会引发实现定义的信号。

- Lundin

7

除了其他提到的问题之外，具有无符号数学环绕功能使得无符号整数类型表现为抽象代数群（这意味着，X和Y任意一对值，都将存在某些其他值Z，使得X+Z如果适当地转换，将等于Y，而Y-Z如果适当地转换，将等于X）。如果无符号值仅仅是存储位置类型而不是中间表达式类型（例如，如果没有最大整数类型的无符号等效类型，并且对无符号类型进行算术运算就像它们首先被转换为较大的有符号类型一样，则不需要定义环绕行为，但在没有可加逆元素的情况下进行计算很难。

这在实际使用中具有环绕行为非常有用——例如，在TCP序列号或某些算法（如哈希计算）中。它也可能在需要检测溢出的情况下有所帮助，因为执行计算并检查是否溢出通常比预先检查是否会溢出更容易，特别是如果计算涉及最大可用整数类型。

- supercat

我不太明白为什么有加法逆元会有帮助？实际上我想不出任何溢出行为真正有用的情况... - sleske

@sleske：为了方便人类阅读，使用十进制。如果一个能源计量器读数为0003，上次读数为9995，这是否意味着使用了-9992单位的能量，还是使用了0008单位的能量？使0003-9995得出0008可以轻松计算后者的结果。如果它产生-9992将使它有点尴尬。然而，无法做到任何一种情况都需要将0003与9995进行比较，注意到它更小，进行反向减法，从9999中减去该结果，并加1。 - supercat

@sleske：对于TCP序列号等内容，最好有一种类型进行包装，就像能源计量示例中一样，这样代码就不需要将序列号从0xFFFFFFFC到0x00000007的情况与从0x00000002到0x0000000D的情况区别对待。至于a、b和c的示例，即使一个人不关心a+b或(a+b)-c超出所使用类型范围的任何情况，但他们往往会关心(b-c)超出该类型范围的情况。然而，如果该类型遵守算术法则... - supercat

1

使得(a+b)-c等于a+(b-c)，无论b-c的算术值是否可在该类型中表示，替换都将是有效的，而且不受(b-c)可能取值范围的影响。 - supercat

感谢您的解释。我尝试将其编辑到您的答案中 - 请随意更正。 - sleske

显示剩余2条评论

3

也许未定义的算术是因为无符号数字形成2^n的整数模，其中n是无符号数字的宽度。无符号数字只是用二进制数字表示的整数，而不是十进制数字。在模系统中执行标准操作是被理解的。 OP的引用涉及到这一事实，但也强调了只有一种明确、逻辑上正确的方式来表示二进制无符号整数。相比之下，有符号数通常使用二补码表示，但标准（第6.2.6.2节）描述了其他选择。二补码表示允许某些操作在二进制格式下更有意义。例如，对负数进行递增与对正数进行递增相同（带溢出条件）。在机器级别上，某些操作对有符号和无符号数字来说是相同的。然而，在解释这些操作的结果时，某些情况是不合理的-正向和负向溢出。此外，溢出结果取决于底层的有符号表示形式。

- yth

对于一个结构体来成为一个域，除了加法单位元素之外的每个元素都必须有乘法逆元。当N等于1或质数时，模N整数结构才能成为一个域[当N==1时，是退化域]。你觉得我在回答中漏掉了什么吗？ - supercat

你是对的。我被质数幂模搞混了。原始回复已经编辑过了。 - yth

这里特别混乱的是，存在一个2^n次方阶域，但它与模2^n的整数环不同构。 - Kevin Ventullo

而且，2^31-1是一个梅森素数（但2^63-1不是素数）。因此，我的原始想法被破坏了。另外，整数大小在过去是不同的。因此，我的想法最多只能算是修正主义的。 - yth

无符号整数形成一个环（而不是域），取低位部分也会形成一个环。在整个值上执行操作然后截断，将等效于仅在较低部分执行操作。在我看来，这几乎肯定是要考虑的因素。 - supercat

0

最主要的技术原因是，尝试在无符号整数中捕获溢出需要更多的移动部件（异常处理）和处理器（异常抛出）。

C和C++不会让你为此付出代价，除非你使用有符号整数。这并不是一个硬性规定，正如你将在最后看到的那样，但这就是它们处理无符号整数的方式。在我看来，这使得有符号整数成为了奇怪的存在，而不是无符号整数，但是他们提供这种基本差异是可以的，程序员仍然可以执行具有溢出的明确定义的有符号操作。但是，为此必须进行强制转换。

因为：

无符号整数具有明确定义的溢出和下溢
从有符号 -> 无符号int的转换是明确定义的，概念上将[uint的名称]_MAX-1添加到负值中，以将它们映射到扩展的正数范围
从无符号 -> 有符号int的转换是明确定义的，概念上从超过有符号类型最大值的正值中扣除[uint的名称]_MAX-1，以将它们映射到负数）

您可以始终使用具有明确定义的溢出和下溢行为的算术运算，其中有符号整数是您的起点，尽管需要通过先转换为无符号整数，然后在完成后再转回来。

int32_t x = 10;
int32_t y = -50;  

// writes -60 into z, this is well defined
int32_t z = int32_t(uint32_t(y) - uint32_t(x));

如果CPU使用2的补码（几乎所有CPU都是如此），则在相同宽度的有符号和无符号整数类型之间进行转换是免费的。但是，如果您的目标平台出于某种原因不使用2的补码来表示有符号整数，则在uint32和int32之间进行转换时将付出一些转换代价。

但是，在使用比int更小的位宽时要小心

通常，如果您依赖于无符号溢出，那么您正在使用较小的字宽，例如8位或16位。这些将在任何时候都升级为有符号int（C具有绝对疯狂的隐式整数转换规则，这是C最大的隐藏陷阱之一），请考虑：

unsigned char a = 0;  
unsigned char b = 1;
printf("%i", a - b);  // outputs -1, not 255 as you'd expect

为了避免这种情况，当你依赖于某个类型的宽度时，无论在操作的中间过程中你认为这是不必要的，你都应该始终将其转换为你想要的类型。这将对临时值进行转换，并获得你期望的有符号性和截断值。转换几乎总是免费的，事实上，你的编译器可能会因此而感谢你，因为它可以更积极地优化你的意图。

unsigned char a = 0;  
unsigned char b = 1;
printf("%i", (unsigned char)(a - b));  // cast turns -1 to 255, outputs 255

- Anne Quinn

尝试在无符号整数中捕获溢出需要更多的移动部件。你是指有符号的吗？ - Olli Niemitalo

“从无符号 -> 有符号 int 的强制转换是明确定义的”这种说法是不正确的；如果结果不能在有符号类型中表示，则从无符号到有符号的转换会产生一个实现定义的结果。（或引发实现定义的信号。）大多数实现确实像您描述的那样进行包装，但标准并不保证。C17 6.3.1.3p3 - Nate Eldredge

0

C++只是从C中继承了这种行为。

我认为，在C语言的使用者和实现者之间已经存在了一种脱节。C语言最初被设计为汇编语言的可移植替代品，最初并没有像现在这样的标准，只有一本描述该语言的书籍。在早期的C语言中，低级平台特定的黑客技巧是常见且被接受的做法。许多真正的C程序员仍然认为C语言是这样的。

当引入标准时，其目标主要是标准化现有的做法。有些事情被留空或者是实现定义的。我不确定有多少注意力被放在了哪些东西是未定义的，哪些东西是实现定义的上。

在C语言标准化时，二进制补码是最常见的方法，但其他方法也存在，因此C语言不能直接要求使用二进制补码。

如果您阅读https://www.open-std.org/jtc1/sc22/wg14/www/C99RationaleV5.10.pdf中关于标准C的原理解释，他们讨论了提升语义的选择，他们决定采用“值保留”的语义更安全，但是他们基于这样的假设做出了这个决定，即大多数实现使用二进制补码，并以明显的方式静默处理环绕。

然而，编译器供应商在某个时候开始将有符号溢出视为优化机会。这已经将有符号溢出变成了一个主要的陷阱。除非您仔细检查每个算术操作以确保它不会溢出，否则可能会触发未定义行为。

一旦触发了未定义行为，“任何事情都可能发生”。实际上，这意味着变量实际包含的值可能超出编译器认为它可以包含的值范围。这反过来又可能使边界检查无效。

- plugwash

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Pascal Cuoq · Accepted Answer

The historical reason most C compilers used overflow behavior that was easiest to implement with the integer representation they used. The representation used by the CPU determined the overflow behavior. However, only signed values may differ in representation: one's complement, two's complement, sign-magnitude. For an unsigned type, there is no reason to allow variation because there is only one obvious binary representation (the standard only allows binary representation). According to C99 6.2.6.1:3, values stored in unsigned bit-fields and objects of type unsigned char must be represented using pure binary notation. Additionally, C99 6.2.6.2:2 is also relevant.

如果符号位为1，则该值将根据以下一种方式进行修改： — 具有符号位0的相应值被取反（符号-数值法）; — 符号位为-(2^N)（二进制补码）; — 符号位为-(2^N-1)（一的补码）。

现在，所有的处理器都使用二进制补码表示，但有符号算术溢出仍然是未定义的，并且编译器制造商希望它保持未定义，因为他们使用这种未定义性来帮助优化。请参见 Ian Lance Taylor 的博客文章或 Agner Fog 的投诉，以及对他的错误报告的答案。