up vote 128 down vote favorite
33

Unsigned integer overflow is well defined by both the C and C++ standards. For example, the C99 standard (§6.2.5/9) states

A computation involving unsigned operands can never overflow, because a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting type.

However, both standards state that signed integer overflow is undefined behavior. Again, from the C99 standard (§3.4.3/1)

An example of undefined behavior is the behavior on integer overflow

Is there an historical or (even better!) a technical reason for this discrepancy?

share|improve this question
32  
Probably because there is more than one way of representing signed integers. Which way is not specified in the standard, at least not in C++. – juanchopanza Aug 12 '13 at 20:06
    
Useful link: en.wikipedia.org/wiki/Signed_number_representations – Robᵩ Aug 12 '13 at 20:07
5  
What juanchopanza said makes sense. As I understand it, the original C standard in a large part codified existing practice. If all implementations at that time agreed on what unsigned "overflow" should do, that's a good reason for getting it standardized. They didn't agree on what signed overflow should do, so that did not get in the standard. – hvd Aug 12 '13 at 20:07
2  
@DavidElliman Unsigned wraparound on addition is easily detectable (if (a + b < a)) too. Overflow on multiplication is hard for both signed and unsigned types. – hvd Aug 12 '13 at 20:10
3  
@DavidElliman: It is not only an issue of whether you can detect it, but what the result is. In a sign + value implementation, MAX_INT+1 == -0, while on a two's complement it would be INT_MIN – David Rodríguez - dribeas Aug 12 '13 at 20:11
up vote 99 down vote accepted

The historical reason is that most C implementations (compilers) just used whatever overflow behaviour was easiest to implement with the integer representation it used. C implementations usually used the same representation used by the CPU - so the overflow behavior followed from the integer representation used by the CPU.

In practice, it is only the representations for signed values that may differ according to the implementation: one's complement, two's complement, sign-magnitude. For an unsigned type there is no reason for the standard to allow variation because there is only one obvious binary representation (the standard only allows binary representation).

Relevant quotes:

C99 6.2.6.1:3:

Values stored in unsigned bit-fields and objects of type unsigned char shall be represented using a pure binary notation.

C99 6.2.6.2:2:

If the sign bit is one, the value shall be modified in one of the following ways:

— the corresponding value with sign bit 0 is negated (sign and magnitude);

— the sign bit has the value −(2N) (two’s complement);

— the sign bit has the value −(2N − 1) (one’s complement).

Nowadays, all processors use two's complement representation, but signed arithmetic overflow remains undefined and compiler makers want it to remain undefined because they use this undefinedness to help with optimization. See for instance this blog post by Ian Lance Taylor or this complaint by Agner Fog, and the answers to his bug report.

share|improve this answer
3  
The important note here, though, is that there remain no architectures in the modern world using anything other than 2's complement signed arithmetic. That the language standards still allow for implementation on e.g. a PDP-1 is a pure historical artifact. – Andy Ross Aug 12 '13 at 20:12
6  
@AndyRoss but there are still systems (OS + compilers, admittedly with an old history) with one's complement and new releases as of 2013. An example: OS 2200. – ouah Aug 12 '13 at 20:26
3  
@Andy Ross would you consider "no architectures ... using anything other than 2's complement ..." today includes the gamut of DSPs and embedded processors? – chux Aug 12 '13 at 20:27
6  
@AndyRoss: While there are “no” architectures using anything other than 2s complement (for some definition of “no”), there definitely are DSP architectures that use saturating arithmetic for signed integers. – Stephen Canon Aug 12 '13 at 20:33
6  
Saturating signed arithmetic is definitely compliant with the standard. Of course the wrapping instructions must be used for unsigned arithmetic, but the compiler always has the information to know whether unsigned or signed arithmetic is being done, so it can certainly choose the instructions appropriately. – caf Aug 13 '13 at 1:38
up vote 9 down vote

Aside from Pascal's good answer (which I'm sure is the main motivation), it is also possible that some processors cause an exception on signed integer overflow, which of course would cause problems if the compiler had to "arrange for another behaviour" (e.g. use extra instructions to check for potential overflow and calculate differently in that case).

It is also worth noting that "undefined behaviour" doesn't mean "doesn't work". It means that the implementation is allowed to do whatever it likes in that situation. This includes doing "the right thing" as well as "calling the police" or "crashing". Most compilers, when possible, will choose "do the right thing", assuming that is relatively easy to define (in this case, it is). However, if you are having overflows in the calculations, it is important to understand what that actually results in, and that the compiler MAY do something other than what you expect (and that this may very depending on compiler version, optimisation settings, etc).

share|improve this answer
12  
Compilers do not want you to rely on them doing the right thing, though, and most of them will show you so as soon as you compile int f(int x) { return x+1>x; } with optimization. GCC and ICC do, with default options, optimize the above to return 1;. – Pascal Cuoq Aug 12 '13 at 20:18
    
For an example program that gives different results when faced with int overflow depending on optimization levels, see ideone.com/cki8nM I think this demonstrates that your answer gives bad advice. – Magnus Hoff Aug 12 '13 at 20:19
    
I have amended that part a bit. – Mats Petersson Aug 12 '13 at 20:29
    
If a C were to provide a means of declaring a "wrapping signed two's complement" integer, no platform that can run C at all should have much trouble supporting it at least moderately efficiently. The extra overhead would be sufficient that code shouldn't use such a type when wrapping behavior isn't required, but most operations on two's complement integers are identical to those on an unsigned integers, except for comparisons and promotions. – supercat Feb 10 '14 at 21:09
1  
Negative values need to exist and "work" for the compiler to work correctly, It is of course entirely possible to work around the lack of signed values within a processor, and use unsigned values, either as ones complement or twos complement, whichever makes most sense based on what the instruction set is. It would typically be significantly slower to do this than having hardware support for it, but it's no different from processors that doesn't support floating point in hardware, or similar - it just adds a lot of extra code. – Mats Petersson May 3 '15 at 22:04
up vote 4 down vote

In addition to the other issues mentioned, having unsigned math wrap makes the unsigned integer types behave as abstract algebraic groups (meaning that, among other things, for any pair of values X and Y, there will exist some other value Z such that X+Z will, if properly cast, equal Y and Y-Z will, if properly cast, equal X). If unsigned values were merely storage-location types and not intermediate-expression types (e.g. if there were no unsigned equivalent of the largest integer type, and arithmetic operations on unsigned types behaved as though they were first converted them to larger signed types, then there wouldn't be as much need for defined wrapping behavior, but it's difficult to do calculations in a type which doesn't have e.g. an additive inverse.

This helps in situations where wrap-around behavior is actually useful - for example with TCP sequence numbers or certain algorithms, such as hash calculation. It may also help in situations where it's necessary to detect overflow, since performing calculations and checking whether they overflowed is often easier than checking in advance whether they would overflow, especially if the calculations involve the largest available integer type.

share|improve this answer
    
I don't quite follow - why does it help to have an additive inverse? I can't really think of any situation where the overflow behaviour is actually useful... – sleske Mar 14 '16 at 11:02
    
@sleske: Using decimal for human-readability, if an energy meter reads 0003 and the previous reading was 9995, does that mean that -9992 units of energy were used, or that 0008 units of energy were used? Having 0003-9995 yield 0008 makes it easy to calculate the latter result. Having it yield -9992 would make it a little more awkward. Not being able to have it do either, however, would make it necessary to compare 0003 to 9995, notice that it's less, do the reverse subtraction, subtract that result from 9999, and add 1. – supercat Mar 14 '16 at 15:00
    
@sleske: It's also very useful for both humans and compilers to be able to apply the associative, distributive, and commutative laws of arithmetic to rewrite expressions and simplify them; for example, if the expression a+b-c is computed within a loop, but b and c are constant within that loop, it may be helpful to move computation of (b-c) outside the loop, but doing that would require among other things that (b-c) yield a value which, when added to a, will yield a+b-c, which in turn requires that c have an additive inverse. – supercat Mar 14 '16 at 15:09
    
:Thanks for the explanations. If I understand it correctly, your examples all assume that you actually want to handle the overflow. In most cases I have encountered, the overflow is undesirable, and you want to prevent it, because the result of a calculation with overflow is not useful. For example, for the energy meter you probably want to use a type such that overflow never occurs. – sleske Mar 14 '16 at 15:27
    
@sleske: For things like TCP sequence numbers, it's most useful to have a type which wraps just as in the energy-meter example, so code doesn't need to treat the case where a sequence number goes from 0xFFFFFFFC to 0x00000007 any differently from the case where it goes from 0x00000002 to 0x0000000D. As for the example with a, b, and c, even if one doesn't care about any cases where a+b or (a+b)-c would be outside the range of the type one is using, one may very often care about cases where (b-c) is outside the range of that type. If the type obeys the laws of arithmetic, however, ... – supercat Mar 14 '16 at 15:33
up vote 1 down vote

First of all, please note that C11 3.4.3, like all examples and foot notes, is not normative text and therefore not relevant to cite!

The relevant text that states that overflow of integers and floats is undefined behavior is this:

C11 6.5/5

If an exceptional condition occurs during the evaluation of an expression (that is, if the result is not mathematically defined or not in the range of representable values for its type), the behavior is undefined.

A clarification regarding the behavior of unsigned integer types specifically can be found here:

C11 6.2.5/9

The range of nonnegative values of a signed integer type is a subrange of the corresponding unsigned integer type, and the representation of the same value in each type is the same. A computation involving unsigned operands can never overflow, because a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting type.

This makes unsigned integer types a special case.

Also note that there is an exception if any type is converted to a signed type and the old value can no longer be represented. The behavior is then merely implementation-defined, although a signal may be raised.

C11 6.3.1.3

6.3.1.3 Signed and unsigned integers

When a value with integer type is converted to another integer type other than _Bool, if the value can be represented by the new type, it is unchanged.

Otherwise, if the new type is unsigned, the value is converted by repeatedly adding or subtracting one more than the maximum value that can be represented in the new type until the value is in the range of the new type.

Otherwise, the new type is signed and the value cannot be represented in it; either the result is implementation-defined or an implementation-defined signal is raised.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.