Why is unsigned integer overflow defined behavior but signed integer overflow isn't?

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).

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.

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.

Perhaps another reason for why unsigned arithmetic is defined is because unsigned numbers form integers modulo 2^n, where n is the width of the unsigned number. Unsigned numbers are simply integers represented using binary digits instead of decimal digits. Performing the standard operations in a modulus system is well understood.

The OP's quote refers to this fact, but also highlights the fact that there is only one, unambiguous, logical way to represent unsigned integers in binary. By contrast, Signed numbers are most often represented using two's complement but other choices are possible as described in the standard (section 6.2.6.2).

Two's complement representation allows certain operations to make more sense in binary format. E.g., incrementing negative numbers is the same that for positive numbers (expect under overflow conditions). Some operations at the machine level can be the same for signed and unsigned numbers. However, when interpreting the result of those operations, some cases don't make sense - positive and negative overflow. Furthermore, the overflow results differ depending on the underlying signed representation.

C++ just picks up this behaviour from C.

I believe that with C that a disconnect has developed between it's users and it's implementers. C was designed as a more portable alternative to assembler and originally did not have a standard as such, just a book describing the language. In early C low level platform specific hacks were common and accepted practice. Many real-world C programmers still think of C this way.

When a standard was introduced, it's goal was largely to standardise existing practice. Some things were left undefined or implementation defined. I'm not convinced that much attention was paid to which stuff was undefined and which stuff was implementation defined.

At the time when C was standardised, twos complement was the most common approach, but other approaches were around, so C couldn't outright require twos complement.

If you read the rationale for standard C at https://www.open-std.org/jtc1/sc22/wg14/www/C99RationaleV5.10.pdf where they discuss the choice of promotion semantics they decided that the "value preserving" semantics were safer, however they made this decision based on the assumption that most implementations used twos complement and handled wraparound quietly in the obvious manner.

Compiler vendors at some point however started treating signed overflow as an optimisation opportunity. This has turned signed overflow into a major footgun. Unless you carefully check every arithmetic operation to make sure it can't overflow you can end up triggering undefined behaviour.

Once undefined behaviour is triggered, "anything can happen". What that means in practice is that the value a variable actually contains may be outside the range of values the compiler assumes it can contain. That in turn can render bounds checking ineffective.

This is an old question, but there aren't many examples of the possible UB here to go with the reasoning. Here is one:

#include <limits.h>
#include <stdio.h>

int main(void) {
    int num = INT_MAX;
    if (num > 0)
        printf("%d > 0\n", num);
    if (num + 1 > 0)
        printf("%d > 0\n", num + 1);
    return 0;
}

With x86 GCC (13.2), both lines will print. With x86 Clang (17.0.1), only the first line will print.

Here is a link to try for yourself: https://godbolt.org/z/Gszd55bjs

What can happen here is that compilers are more or less allowed to assume that signed integers are infinite. So if a > x, then a + 1 is also > x - which is true for math, but not for fixed-size wrapping representations. This can be used for optimization, but the example here has the same results at -O0 as -O3

Moving the inner logic to a different file separate from the num definition (making it opaque) gets both compilers print both lines, which is something that could be pretty surprising when refactoring.

The most technical reason of all, is simply that trying to capture overflow in an unsigned integer requires more moving parts from you (exception handling) and the processor (exception throwing).

C and C++ won't make you pay for that unless you ask for it by using a signed integer. This isn't a hard-fast rule, as you'll see near the end, but just how they proceed for unsigned integers. In my opinion, this makes signed integers the odd-one out, not unsigned, but it's fine they offer this fundamental difference as the programmer can still perform well-defined signed operations with overflow. But to do so, you must cast for it.

Because:

• unsigned integers have well defined overflow and underflow
• casts from signed -> unsigned int are well defined, [uint's name]_MAX - 1 is conceptually added to negative values, to map them to the extended positive number range
• casts from unsigned -> signed int are well defined, [uint's name]_MAX - 1 is conceptually deducted from positive values beyond the signed type's max, to map them to negative numbers)

You can always perform arithmetic operations with well-defined overflow and underflow behavior, where signed integers are your starting point, albeit in a round-about way, by casting to unsigned integer first then back once finished.

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));

Casts between signed and unsigned integer types of the same width are free, if the CPU is using 2's compliment (nearly all do). If for some reason the platform you're targeting doesn't use 2's Compliment for signed integers, you will pay a small conversion price when casting between uint32 and int32.

But be wary when using bit widths smaller than int

usually if you are relying on unsigned overflow, you are using a smaller word width, 8bit or 16bit. These will promote to signed int at the drop of a hat (C has absolutely insane implicit integer conversion rules, this is one of C's biggest hidden gotcha's), consider:

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

To avoid this, you should always cast to the type you want when you are relying on that type's width, even in the middle of an operation where you think it's unnecessary. This will cast the temporary and get you the signedness AND truncate the value so you get what you expected. It's almost always free to cast, and in fact, your compiler might thank you for doing so as it can then optimize on your intentions more aggressively.

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

Building on the answers about using numbers as a ring mod 2^32, some hashing and checksum algorithms are built to be performed modulo a word size. For example, for a CRC code, common implementations choose a polynomial so that they can be computed very quickly using an unsigned 16-bit integer (Bluetooth, USB), 32-bit integer (Ethernet, GZIP, MPEG-2, Adler-32), 64-bit integer, etc. In these cases, the math operates on a polynomial over the finite field with 2 elements, which isn't important for this answer aside from just saying it maps directly to a binary integer and overflow is completely intended. Also, MD5 and SHA-1 are designed to use unsigned 32-bit ints with wrapping.

In my opinion, it's much safer to explicitly say when you want this overflow behavior. But getting the compiler to not warn about all the false positives without manually annotating every math operation is difficult. Linus Torvalds ranted last year against a proposal for the Linux kernel for C operator overloading by handling overflows with handlers:

I'm still entirely unconvinced.

The thing is, wrap-around is not only well-defined, it's common, and EXPECTED.

Example:

static inline u32 __hash_32_generic(u32 val) { return val * GOLDEN_RATIO_32; }

and dammit, I absolutely DO NOT THINK we should annotate this as some kind of "special multiply".

I have no idea how many of these exist. But I am 100% convinced that making humans annotate this and making the source code worse is absolutely the wrong approach.

Basically, unsigned arithmetic is well-defined as wrapping around, and it is so for a good reason.

So I'm going to have a HARD REQUIREMENT that any compiler complaints need to be really really sane. They need to detect when people do things like this on purpose, and they need to SHUT THE ^&% UP about the fact that wrap-around happens.

Any tool that is so stupid as to complain about wrap-around in the above is a BROKEN TOOL THAT NEEDS TO BE IGNORED.

Really. This is non-negotiable.

This is similar to the whole

    unsigned int a, b;

    if (a+b < a) ..

kind of pattern: a tool that complains about wrap-around in the above is absolutely broken sh*t and needs to be ignored.

So I think you need to limit your wrap-around complaints, and really think about how to limit them. If you go "wrap-around is wrong" as some kind of general; rule, I'm going to ignore you, and I'm going to tell people to ignore you, and refuse any idiotic patches that are the result of such idiotic rules.

Put another way the absolute first and fundamental thing you should look at is to make sure tools don't complain about sane behavior.

Until you have done that, and taken this seriously, this discussion is not going to ever result in anything productive.

Any kind of mindless "this can wrap around" is inexcusable.

And later:

It needs to be smarter than that. And yes, that means exactly taking into account how the result of the possible wrap-around is actually used.

If it's used as a size or as an array index, it might be a problem. But if it's used for masking and then a masked version is used for an index, it clearly is NOT a problem.

IOW, exactly the same as "a+b < a". Yes, "a+b" might wrap around, but if the use is to then compare it with one of the addends, then clearly such a wrap-around is fine.

A tool that doesn't look at how the result is used, and just blindly says "wrap-around error" is a tool that I think is actively detrimental.

And no, the answer is ABSOLUTELY NOT to add cognitive load on kernel developers by adding yet more random helper types and/or functions.

We already expect a lot of kernel developers. We should not add on to that burden because of your pet project.

Put another way: I'm putting the onus on YOU to make sure your pet project is the "Yogi Bear" of pet projects - smarter than the average bear.

As long as you are approaching this from a "this puts the onus on others", YOU are the problem.

Be the solution, not the problem.

          Linus