How does addition of negative integers work in C?

Question

Given this simple code snippet:

#include <stdio.h>
#include <stdint.h>

int main() {
    int8_t a = -1;
    printf("Dec: %d, Hex: %hhx\n", a, a);
    int8_t b = a + 1;
    printf("Dec: %d, Hex: %hhx\n", b, b);
    return 0;
}

The result is:

Dec: -1, Hex: ff
Dec: 0, Hex: 0

which makes sense and it looks my system is using two's complement to implement negative integers.

But a is an 8-bit signed integer. When adding 1 to 0xff, it should result in an integer overflow. And according to this question, signed integer overflow is not a defined behavior.

Thus, how does addition work for an 8-bit negative integer such that it avoids undefined behavior?

Does it have something to do with integer promotion? If so, how does it work at a low level?

Update: I appreciate all answers. After reading all the answers, I am still confused about promotion and wraparound. E.g., when an signed integer with the biggest data type is used, does it still do promotion and wraparound? Given this code:

int main() {
    intmax_t a = -1;
    printf("Dec: %ld, Hex: %lx\n", a, a);
    intmax_t b = a + 1;
    printf("Dec: %ld, Hex: %lx\n", b, b);
    return 0;
}

The result is:

Dec: -1, Hex: ffffffffffffffff
Dec: 0, Hex: 0

The result is still correct and I would like to know why since there is no more promotion can be done here, right?

Also, I am especially confused about the statement of "0xff + 1" versus "-1 + 1" such as:

You're not actually adding 1 to 0xff. You're adding 1 to -1. It's just that -1 is represented as 0xff in a int8_t.

I am sorry, but in the computer, as far as I know, there is no idea of "-1". It's using binary representation of "-1" to do all kinds of addition, right? So, my question is that when binary representation is used to conduct addition 0xffffffffffffffff + 1, why doesn't it overflow. What's happening under the hood?

Answer 1

Unsigned integers do not overflow only wrap around. When you analyze how two's complement numbers work under the hood - you analyze unsigned integers.

Signed integers overflow (or underflow) occurs when it gets a value larger than the maximum or minimum signed value which can be stored in that integer.

For int8_t those values are -128 & 127. So when you want to add or subtract 1 only -128 - 1 or 127 + 1 will result in overflow. -1 + 1 does not.

How does it work under the hood?

-1 in two's complement (8 bits):

First, represent 1 in binary, then invert the bits and add one to find -1.

Binary representation of `+1`: `00000001`
Invert the bits: `11111110`
Add one: `11111111`

So, -1 is represented as 11111111 in two's complement.

• +1 in binary (8 bits): 00000001
• Addition

       11111111  (-1 in two's complement)
     + 00000001  (+1 in binary)
       --------
      100000000  (9 bits result, but as "normal" 
      unsigned number it wraps around so we get `00000000`)

Answer 2

https://en.cppreference.com/w/c/language/conversion:

The arguments of the following arithmetic operators undergo implicit conversions for the purpose of obtaining the common real type, which is the type in which the calculation is performed:

• binary arithmetic *, /, %, +, -

...

Otherwise, both operands are integers. Both operands undergo integer promotions (see below)

Integer promotions

Integer promotion is the implicit conversion of a value of any integer type with rank less or equal to rank of int or of a bit-field of type _Bool(until C23)bool(since C23), int, signed int, unsigned int, to the value of type int or unsigned int.

If int can represent the entire range of values of the original type (or the range of values of the original bit-field), the value is converted to type int. Otherwise the value is converted to unsigned int.

In other words, no addition is ever performed on integer arguments smaller than int.

Here, in int8_t b = a + 1; statement:

1. int8_t a with value of -1 is first signed-extended to int size and then signedness is changed to that of int (no change here). The result of the integer promotion is (int)-1.

2. The int result of addition gets truncated back to int8_t, in implementation-specific manner if int8_t cannot store the value of that int.

In other words, ((int)(int_8)(-1)) + 1 == (int)0, and that is perfectly well-defined.

Answer 3

But now my question is that a is an 8-bit signed integer. When adding 1 to 0xff, it should results to an integer overflow

You're not actually adding 1 to 0xff. You're adding 1 to -1. It's just that -1 is represented as 0xff in a int8_t. In a two's complement system this is effectively the same as adding the representations, but that's really an implementation detail.

Also, there is integer promotion occurring in the initialization of b:

int8_t b = a + 1;

Generally speaking, anytime a type smaller that int is used in an expression it is first promoted to int.

So the int8_t value of -1 whose representation is 0xff is promoted to the int value of -1 whose representation is 0xffffffff. This is added to the int value 1 resulting in the int value 0. The two's complement representation of these number effectively wraps around, but the actual result does not so it's still well defined.

Although not explicitly defined in the standard, overflow is when the result of an expression lies outside the range of the expression's type. It does not necessarily mean wraparound. The exception to this is that expressions involving unsigned operands are explicitly stated to wraparound and do not result in overflow.

Regarding your updates:

when an signed integer with the biggest data type is used, does it still do promotion and wraparound?

There's no promotion involved when a type bigger than int is used, but the representation can still wrap around, and in the case of two's complement that's what it does, just like in your previous case.

So, my question is that when binary representation is used to do addition, why doesn't it overflow?

As I mentioned before, overflow has to do with the resulting value, not the representation.

Here's another example:

int x = INT_MAX + 1;

Assuming two's complement representation and a 32-bit int, INT_MAX has a value of 2³¹-1 and a representation of 0x7fffffff. Adding 1 to INT_MAX has a result goes outside of the range of an int and therefore produces overflow and triggers undefined behavior. In this case there is no wraparound of the representation. From a strictly binary standpoint, adding 1 to the representation 0x7fffffff results in 0x80000000, however that doesn't matter when the resulting value goes outside the range of an int.

Because overflow is undefined behavior, a compiler is allowed to assume undefined behavior does not exist and perform optimizations based on that assumption.

For example:

int i;
for (i=0; i!=-1; i++) {
    printf("hello\n");
}

GCC on optimization levels 2 and 3 will optimize this code into an infinite loop under the assumption that signed integer overflow will not occur.

Answer 4

… it looks my system is using Two's complement to implement negative integers.

There is nothing in the output that makes it look like your C implementation uses two’s complement. The program will produce the same output regardless of whether the C implementation uses two’s complement, one’s complement, or sign-and-magnitude.

Let’s look at the first line of output, Dec: -1, Hex: ff, which comes from int8_t a = -1; and printf("Dec: %d, Hex: %hhx\n", a, a);. The code int8_t a = -1; obviously sets a to −1, and that is what printf prints for the %d.

For %hhx, you are intended to pass a signed char or unsigned char. However, these would be automatically promoted to int, so the argument passed to printf, and the parameter used by it, is always an int. C 2018 7.21.6.1 7 tells us “its value shall be converted to signed char or unsigned char before printing”. With x, it is converted to an unsigned char. C 2018 6.3.1.3 2 tells us how this conversion is performed:

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

“One more than the maximum value that can be represented in” unsigned char is 256 (in your C implementation and all common C implementations). You passed −1, so it is converted to unsigned char by adding 256, yielding 255, which is representable in unsigned char. Then printf formatted this in hexadecimal, producing ff.

Observe this result does not depend on two’s complement. Given an argument of −1, %hhx produces ff because −1 + 256 = 255 = FF₁₆. How any of these numbers are represented is irrelevant.

When adding 1 to 0xff, it should results to an integer overflow.

Nothing in your program adds 1 to 0xff. −1 was displayed as ff by printf with %hhx, but that does not change the fact that the value of a is −1.

Also, adding 1 to 0xff does not overflow. In arithmetic, operands are promoted to at least the int type, and adding 1 to 255 produces 256, which is representable in an int.

If you did have int8_t b = 256;, 256 would not be representable in int8_t. In that case, the conversion is implementation-defined, meaning the C implementation must document what the resulting value or signal would be.

Does it have something to do with integer promotion? If so, please explain how it works in low-level.

Given an int8_t with value −1 in a + 1, the C implementation converts the int8_t to an int. It may do this by sign extension or by other means suitable for that particular C implementation. The result is −1 in an int type. Then −1 and 1 are added.

If two’s complement is used, −1 in a 32-bit int is FFFFFFFF₁₆, and adding 1 produces all zeros with a carry out of the 32 bits, which is discarded, yielding 0.

If one’s complement is used, −1 in a 32-bit int is FFFFFFFE₁₆, and adding 1 produces FFFFFFFF₁₆, which is −0 in one’s complement, equal to +0. (It may also produce 00000000₁₆ directly, depending on implementation.)

If sign-and-magnitude is used, −1 in a 32-bit int is 80000001₁₆, and adding one produces 80000000₁₆, which is −0 in sign-and-magnitude, equal to +0. (It may also produce 00000000₁₆ directly, depending on implementation.)

In all cases, the result of adding −1 and 1 is equal to 0.