current community

your communities

more stack exchange communities

Stack Exchange
tour help
careers 2.0
Take the 2-minute tour ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 50 down vote favorite
7

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
19  
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
2  
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
1  
@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
2  
@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

4 Answers 4

up vote 43 down vote accepted

The historical reason is that 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.

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) (ones’ 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
1  
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
2  
@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
1  
@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
2  
@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
2  
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 5 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 includees 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
4  
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 at 21:09
    
@supercat: You are assuming that the system uses two's complement. What about one's complement, or "sign bit and regular number" (e.g. in 8-bit: 1 = 00000001, -1 = 10000001, 63 = 00111111, -63 = 10111111 - this is how floating point numbers are stores, so it's not beyond the realm of possibility to have this in a integer form too). –  Mats Petersson Feb 11 at 8:25
up vote 1 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.

share|improve this answer
up vote 0 down vote

The overflow bit is set when the highest bit carries over from a summation. This is readily flagged with unsigned numbers, as the highest number is 0b11111111 (8 bits). But for signed numbers, the hardware is not in place because the highest unsigned (8-bit) number is 0b01111111. The hardware carryover bit does not work.

share|improve this answer
1  
This is why processors have both a carry flag and an overflow flag: teaching.idallen.com/dat2343/10f/notes/040_overflow.txt . But I am unsure how this is relevant, since what compilers do for unsigned arithmetic is ignore the flags and give you, say, the lowest 32-bit of the results of the 32-bit operation the program just made. –  Pascal Cuoq Aug 12 '13 at 20:25

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.