Types and how data lives in memory · about 50 min

Two's complement, signed vs unsigned, and overflow

Why this matters

The previous lesson gave each integer type a range. This lesson shows how negative numbers fit into those bytes, and what happens at the edges of the range. These edges cause real disasters: the Ariane 5 rocket was lost to an overflowing conversion, the "Gangnam Style" video broke YouTube's 32-bit view counter, and countless security holes start with a size calculation that wrapped around to a small number. In C, the rules for what happens are different for signed and unsigned types, and one of them is "anything at all". You need to know which.

Unsigned integers: plain binary

An unsigned integer is stored as the binary number you learned two lessons ago. An unsigned char uses 8 bits for values 0 to 255:

  0000 0000 = 0
  0000 0001 = 1
  0111 1111 = 127
  1000 0000 = 128
  1111 1111 = 255

What happens past the top? The hardware simply drops the carry out of the highest bit, so the value wraps around, like a car odometer rolling from 999999 to 000000:

    1111 1010   (250)
  + 0000 1010   ( 10)
  -----------
  1 0000 0100   (260, but only 8 bits are kept)
    0000 0100   (  4)

C defines this behavior for unsigned types: arithmetic is done modulo 2^n, where n is the number of bits. UINT_MAX + 1 is 0, and 0 - 1 is UINT_MAX. This is guaranteed and portable, and it is sometimes exactly what you want (hash functions, checksums, ring buffers). More often it is a bug, because 0 - 1 being four billion is rarely the intended meaning.

#include <stdio.h>

int main(void)
{
    unsigned char odometer = 250;
    odometer = odometer + 10;
    printf("odometer: %d\n", odometer);

    unsigned int u = 0;
    u = u - 1;
    printf("0u - 1 = %u (0x%x)\n", u, u);
    return 0;
}

odometer: 4
0u - 1 = 4294967295 (0xffffffff)

Signed integers: two's complement

How do you store -5 in bits? Several schemes have been tried; every modern computer uses two's complement, and C23 finally requires it (C17 technically allows two older schemes, but no compiler you will meet uses them).

The idea: in an n-bit two's complement number, the top bit is worth minus 2^(n-1) instead of plus. For 8 bits, the place values are:

  place value: -128   64   32   16    8    4    2    1
  0000 0101:      0    0    0    0    0    1    0    1   =    5
  1111 1011:   -128 + 64 + 32 + 16 + 8 +      2 +  1     =   -5
  1000 0000:   -128                                       = -128
  0111 1111:          64 + 32 + 16 + 8 +  4 +  2 +  1     =  127
  1111 1111:   -128 + 127                                 =   -1

Consequences worth memorizing:

The top bit acts as a sign bit: if it is 1, the number is negative.
-1 is all ones (0xFF in 8 bits, 0xFFFFFFFF in 32 bits).
The range is asymmetric: -128 to 127 in 8 bits, -2147483648 to 2147483647 in 32. There is one more negative number than positive, because zero takes one of the non-negative patterns. So -INT_MIN does not fit.
To negate, invert every bit and add 1. 5 is 0000 0101; inverted, 1111 1010; plus 1, 1111 1011, which is -5. The C operator ~ inverts every bit, so ~x + 1 equals -x.

Why this scheme? Because addition works with exactly the same circuit as unsigned addition. Adding -5 and 7:

    1111 1011   (-5)
  + 0000 0111   ( 7)
  -----------
  1 0000 0010   carry dropped -> 0000 0010 = 2

The CPU does not need to know whether the bits are signed. The type in your program tells the compiler which interpretation to use when comparing, dividing, printing or converting.

Same bits, two meanings

Because signed and unsigned values share bit patterns, converting between same-size types keeps the bits and changes only the interpretation (formally: the value is reduced modulo 2^n):

unsigned int bits = -1;
printf("%u = 0x%08x\n", bits, bits);
bits = -128;
printf("0x%08x\n", bits);

4294967295 = 0xffffffff
0xffffff80

  bit pattern     as signed   as unsigned
  1111 1111          -1          255         (8 bits)
  1000 0000        -128          128
  0111 1111         127          127

Signed overflow is undefined behavior

Here is the crucial asymmetry. Unsigned wraparound is defined. Signed overflow is undefined behavior.

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

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

2147483647 + 1 = -2147483648

On x86-64 at -O0, the hardware wraps just as it does for unsigned, so you see a large negative number. But the C standard says nothing about what should happen, and the optimizer is allowed to assume it never happens. For example, gcc with -O2 compiles

int f(int x) { return x + 1 > x; }

into "return 1", with no addition or comparison at all, because for every x where the behavior is defined, x + 1 > x is true. Code that "checks" for overflow by testing whether the result went negative can be deleted by the compiler for the same reason. Undefined behavior is not "you get some wrong number"; it is "the program no longer means anything". There is a whole lesson on it later.

You can make the compiler catch signed overflow at run time with the undefined behavior sanitizer:

$ gcc -std=c17 -g -fsanitize=undefined -o prog main.c
$ ./prog
main.c:7:9: runtime error: signed integer overflow: 2147483647 + 1 cannot be represented in type 'int'
2147483647 + 1 = -2147483648

The right fix is to choose a type with enough range, or to check before the operation that it cannot overflow (for example if (a > INT_MAX - b) before computing a + b, once you know if).

Common mistakes

Counting down with an unsigned variable and expecting it to go below zero. It wraps to a huge number instead. Sizes are unsigned (size_t), so len - 1 when len is 0 is a classic bug.
Mixing signed and unsigned in comparisons. -1 < 0u is false, because -1 is converted to unsigned (4294967295) before comparing. When the operands are variables, gcc warns with -Wextra (comparison of integer expressions of different signedness: 'int' and 'unsigned int'). The next module explains the conversion rules.
Assuming signed overflow wraps. It often does at -O0 and then mysteriously does not at -O2. Do not rely on it.
Negating INT_MIN. -INT_MIN overflows (there is no +2147483648 in an int), and so does abs(INT_MIN).
Storing out-of-range values into small signed types. signed char sc = 200; stores -56 (200 - 256) on gcc; the conversion result is implementation-defined, and -Wall does not even warn. -Wconversion does.

Recap

Unsigned integers are plain binary and wrap modulo 2^n on overflow; this is defined behavior.
Signed integers use two's complement: the top bit is worth -2^(n-1), -1 is all ones, the range is asymmetric, and -x == ~x + 1.
Signed and unsigned types share bit patterns; conversion keeps the bits, reinterpreting them.
Signed overflow is undefined behavior; the optimizer assumes it never happens. Use -fsanitize=undefined to catch it, and pick types or checks that prevent it.

Going further: compile int f(int x) { return x + 1 > x; } with gcc -O2 -S and look at the assembly in the .s file, then do the same with unsigned int. The unsigned version must keep the comparison, because UINT_MAX + 1 > UINT_MAX is false.

Exercises

Exercise 1 · quiz

Encode a negative number

What is -5 as an 8-bit two's complement value?

1000 0101
1111 1010
1111 1011
0000 0101

Answer

1111 1011

Start from +5 = 0000 0101, invert every bit (1111 1010), add 1: 1111 1011. Check it: as an unsigned byte that pattern is 251, and 251 - 256 = -5. "1000 0101" is the sign-magnitude encoding, which C implementations do not use for integers; "1111 1010" is the ones' complement.

Exercise 2 · quiz

Defined or undefined?

Assume 32-bit int. Which of these have well-defined results in C? Select all that apply.

unsigned int u = UINT_MAX; u = u + 1;
int i = INT_MAX; i = i + 1;
unsigned int u = 0; u = u - 1;
int i = INT_MIN; i = i - 1;
unsigned char c = 255; c = c + 1;

Answer

unsigned int u = UINT_MAX; u = u + 1;
unsigned int u = 0; u = u - 1;
unsigned char c = 255; c = c + 1;

Unsigned arithmetic is defined to wrap modulo 2^n: UINT_MAX + 1 is 0 and 0 - 1 is UINT_MAX. The unsigned char case is fine too: c + 1 is computed as int (256) and storing it back into an unsigned char reduces it modulo 256, giving 0. Signed overflow (INT_MAX + 1, INT_MIN - 1) is undefined behavior: the program is wrong, whatever it happens to print.

Exercise 3 · write code

Look at the bit patterns

Storing a negative int value into an unsigned int keeps the same 32 bits (the value is reduced modulo 2^32). Printing that unsigned with %08x therefore shows the two's complement bit pattern in hex.

Store -1, -2 and -128 into unsigned int variables and print them with %08x, exactly:

-1 = ffffffff
-2 = fffffffe
-128 = ffffff80

File: main.c

Starting point

#include <stdio.h>

int main(void)
{
    unsigned int a = -1;
    printf("-1 = %08x\n", a);
    /* -2 and -128 */
    return 0;
}

Example

expected output

-1 = ffffffff
-2 = fffffffe
-128 = ffffff80

Hint 1

Declare unsigned int b = -2; and unsigned int c = -128; and print them like a.

Reference solution

#include <stdio.h>

int main(void)
{
    unsigned int a = -1;
    unsigned int b = -2;
    unsigned int c = -128;
    printf("-1 = %08x\n", a);
    printf("-2 = %08x\n", b);
    printf("-128 = %08x\n", c);
    return 0;
}

Exercise 4 · write code

Negate the hardware way

Write a function

int negate(int x)

that returns -x without using the minus sign at all: use the two's complement rule "invert all the bits, then add 1". The operator ~ inverts every bit of an int.

Your main can contain anything (for example a few test printfs); the check calls negate directly with values such as 5, -7, 0 and 1000000, and also checks that the function body has no - character.

File: main.c

Starting point

#include <stdio.h>

int negate(int x)
{
    return x;   /* fix me: invert and add one */
}

int main(void)
{
    printf("%d\n", negate(5));
    return 0;
}

Hint 1

~x gives x with every bit flipped.

Hint 2

The whole body is one line: return ~x + 1;

Reference solution

#include <stdio.h>

int negate(int x)
{
    return ~x + 1;
}

int main(void)
{
    printf("%d\n", negate(5));
    return 0;
}