Two's complement ranges

Why this matters

A number in a program is stored in a fixed number of bits. A bit is one binary digit, either 0 or 1. An int or an int8_t is a box with a set number of bits, and the box can only hold so many different patterns.

When a result is larger than the box can hold, the value does not grow to fit. It wraps around to a small number that is wrong. Programs that count money, file sizes, or seconds since a start time can hit these limits, and the bug often shows up only with large inputs, long after the code was tested.

The earlier lessons in this module covered how numbers are written in other bases and how characters are stored as numbers. This lesson asks one narrower question: for each integer type, what is the smallest and the largest value it can hold? Then it asks why the answer for negative numbers is not symmetric.

Counting with bits

Start with a box of 3 bits. Each bit is either 0 or 1, so the box has 2 × 2 × 2 = 8 patterns. If the box stores positive numbers only, the 8 patterns stand for 0 to 7:

000 = 0
001 = 1
010 = 2
011 = 3
100 = 4
101 = 5
110 = 6
111 = 7

Each new bit doubles the number of patterns. With n bits there are 2 to the power n patterns, so the largest unsigned value is 2 to the power n, minus 1. A byte is 8 bits. It has 256 patterns, so an unsigned byte holds 0 to 255.

Here is what happens when a result goes past the top. The type std::uint8_t holds 0 to 255. Add 10 to 250 and the true answer is 260, which needs 9 bits. The box keeps only 8 bits, so 260 becomes 4:

#include <cstdint>
#include <iostream>
 
int main() {
    std::uint8_t small = 250;
    small = static_cast<std::uint8_t>(small + 10);
    std::cout << "uint8_t 250 + 10 = " << static_cast<int>(small) << "\n";
    return 0;
}

Output from a run with g++ -std=c++20 -Wall:

uint8_t 250 + 10 = 4

For unsigned types, C++ defines this wrap-around exactly: the result is the true answer taken modulo 2 to the power n (the remainder after dividing by 2 to the power n). The value 260 modulo 256 is 4. This is a rule of the language, not a compiler quirk.

The lines static_cast<std::uint8_t>(...) and static_cast<int>(small) are needed for reasons covered below. For now, read them as "convert to this type".

Negative numbers: two's complement

Programs also need negative numbers. The scheme almost every computer uses for them is called two's complement. Since C++20, the language requires signed integers to use it.

Here is the rule for an 8-bit signed value. The leftmost bit is the sign bit. Instead of standing for +128, it stands for -128. The other seven bits add up as usual, with values 64, 32, 16, 8, 4, 2 and 1.

Work through five patterns:

• 00000101 has the sign bit off. It is 4 + 1, so the value is 5.
• 01111111 has the sign bit off. It is 64 + 32 + 16 + 8 + 4 + 2 + 1, so the value is 127.
• 10000000 has only the sign bit on. It is -128.
• 11111110 is -128 + 126, so the value is -2.
• 11111111 is -128 + 127, so the value is -1.

Two patterns to notice. The pattern for -1 is all ones. Adding 1 to -1 gives 0, and in 8 bits, adding 1 to 11111111 gives 00000000 with a carry out of the top bit that is dropped. So the same adder circuit works for positive and negative numbers. This is the main reason the scheme is used.

The second pattern to notice is that the negative side has one more value than the positive side. There are 256 patterns in total. Zero takes one of the non-negative patterns, so the non-negative side has 128 patterns for 0 to 127, and the negative side has 128 patterns for -128 to -1. There is no pattern left over for +128.

The ranges of the standard integer types

The types with fixed sizes live in the header <cstdint>. Their names say how many bits they have. The table gives the limits for each type. The values were printed by the program in the next section.

Two formulas cover all the signed types. If a signed type has n bits, its smallest value is -(2 to the power n-1) and its largest is 2 to the power n-1, minus 1. For the unsigned types, the largest is 2 to the power n, minus 1, and the smallest is 0.

Check one row by hand. For int16_t, n is 16. Two to the power 15 is 32768. So the range is -32768 to 32767. The table agrees.

Read the limits from the program

Do not memorise these numbers. The standard library can tell you the limits for any type. The header <limits> provides std::numeric_limits<T>, a template (a pattern the compiler fills in for each type) that has min() and max() functions. Pass it the type you care about:

#include <cstdint>
#include <iostream>
#include <limits>
 
int main() {
    std::cout << "int8_t   " << static_cast<int>(std::numeric_limits<std::int8_t>::min())
              << " " << static_cast<int>(std::numeric_limits<std::int8_t>::max()) << "\n";
    std::cout << "uint8_t  " << static_cast<int>(std::numeric_limits<std::uint8_t>::min())
              << " " << static_cast<int>(std::numeric_limits<std::uint8_t>::max()) << "\n";
    std::cout << "int16_t  " << std::numeric_limits<std::int16_t>::min()
              << " " << std::numeric_limits<std::int16_t>::max() << "\n";
    std::cout << "uint16_t " << std::numeric_limits<std::uint16_t>::min()
              << " " << std::numeric_limits<std::uint16_t>::max() << "\n";
    std::cout << "int32_t  " << std::numeric_limits<std::int32_t>::min()
              << " " << std::numeric_limits<std::int32_t>::max() << "\n";
    std::cout << "uint32_t " << std::numeric_limits<std::uint32_t>::min()
              << " " << std::numeric_limits<std::uint32_t>::max() << "\n";
    std::cout << "int64_t  " << std::numeric_limits<std::int64_t>::min()
              << " " << std::numeric_limits<std::int64_t>::max() << "\n";
    std::cout << "uint64_t " << std::numeric_limits<std::uint64_t>::min()
              << " " << std::numeric_limits<std::uint64_t>::max() << "\n";
    return 0;
}

Output from a run:

int8_t   -128 127
uint8_t  0 255
int16_t  -32768 32767
uint16_t 0 65535
int32_t  -2147483648 2147483647
uint32_t 0 4294967295
int64_t  -9223372036854775808 9223372036854775807
uint64_t 0 18446744073709551615

The 8-bit types need static_cast<int>. On common platforms std::int8_t is the same type as signed char, which the stream prints as a character, so without the cast the program would print a character instead of a number. The cast turns the value into a plain int first.

The standard fixes only minimum sizes for the plain types. int must hold at least the 16-bit range, and long long at least the 64-bit range. On a given machine, int may be larger. When the exact size matters, such as when reading a file format, use the fixed-size names from <cstdint>. When you need to know the limits of a plain type, ask std::numeric_limits for them.

Example: adding without silent wrap-around

Knowing the limits lets a program check a result before it happens. The function below adds two int values. It returns a value if the sum fits and reports failure if it does not. The return type std::optional<int> is a box that holds either an int or nothing. Its std::nullopt value means nothing.

#include <limits>
#include <optional>
 
std::optional<int> checked_add(int a, int b) {
    if (b > 0 && a > std::numeric_limits<int>::max() - b) {
        return std::nullopt;
    }
    if (b < 0 && a < std::numeric_limits<int>::min() - b) {
        return std::nullopt;
    }
    return a + b;
}

The check does not write a + b > max directly. That comparison would itself overflow, because the addition happens first. Instead the function moves the addition to the other side. If b is positive, then max() - b is safe to compute, because it never goes below the smallest value. The sum fits exactly when a is not greater than that number. The negative case works the same way with min() - b.

A test program calls the function with four pairs. The digit separators, such as 2'000'000'000, are a C++14 feature that makes large literals easier to read. They are ignored by the compiler.

#include <iostream>
#include <optional>
 
void show(const std::optional<int>& value) {
    if (value) {
        std::cout << *value << "\n";
    } else {
        std::cout << "does not fit\n";
    }
}
 
int main() {
    show(checked_add(2'000'000'000, 100'000'000));
    show(checked_add(2'000'000'000, 147'483'647));
    show(checked_add(-2'000'000'000, -147'483'648));
    show(checked_add(-2'000'000'000, -147'483'649));
    return 0;
}

Output from a run:

2100000000
2147483647
-2147483648
does not fit

The second line is exactly the largest int on this machine. The third line is exactly the smallest. The fourth line goes one below the smallest value, so the function reports failure.

Why negating the smallest value stays negative

Negation is the simplest case where the limits show up. For any ordinary number, -x is the number with the opposite sign. Negating 5 gives -5, and negating -5 gives 5.

Now take the smallest 8-bit value, -128. Its negation should be 128. But the largest int8_t is 127, so 128 does not fit. What pattern does the program produce for -(-128)?

Two's complement negation has a simple recipe: flip every bit, then add 1. Apply it to -128, which is 10000000:

start:   10000000   (-128)
flip:    01111111   (127)
add 1:   10000000   (-128)

The result is -128 again. The number 128 has no pattern in 8 bits as a signed value, so the negation has nowhere to go. The bits wrap around and return the original value.

The same thing happens with 32 bits. The smallest int32_t is -2147483648. Its negation would be 2147483648, which needs 33 bits in the signed form. The pattern wraps back to -2147483648.

Negating in unsigned arithmetic

The wrap-around rule for unsigned types is well defined, so a safe negation can be written with an unsigned type. The idea is to compute 0 - x in unsigned arithmetic, which wraps, and then convert the result back to the signed type.

#include <cstdint>
#include <iostream>
 
std::int8_t negate_wrapping(std::int8_t x) {
    std::uint8_t u = static_cast<std::uint8_t>(0u - static_cast<std::uint8_t>(x));
    return static_cast<std::int8_t>(u);
}
 
int main() {
    std::int8_t lo = -128;
    std::int8_t hi = 127;
    std::cout << "negate_wrapping(-128) = " << static_cast<int>(negate_wrapping(lo)) << "\n";
    std::cout << "negate_wrapping(127)  = " << static_cast<int>(negate_wrapping(hi)) << "\n";
    std::cout << "negate_wrapping(5)    = " << static_cast<int>(negate_wrapping(5)) << "\n";
    std::cout << "negate_wrapping(-5)   = " << static_cast<int>(negate_wrapping(-5)) << "\n";
    return 0;
}

Output from a run:

negate_wrapping(-128) = -128
negate_wrapping(127)  = -127
negate_wrapping(5)    = -5
negate_wrapping(-5)   = 5

For 5, the unsigned value is 5, and 0 - 5 wraps to 251 in 8 bits. The pattern 251 read as a signed 8-bit value is -5. For -128, the unsigned pattern is 128, and 0 - 128 wraps to 128 again, which reads as -128. The conversion back with static_cast<std::uint8_t> keeps only the low 8 bits, so the arithmetic result is always in range.

Why the plain version is a bug

Writing -m directly on the smallest signed value is different. In C++, signed overflow is undefined behaviour. The standard does not say what happens, so the program may do anything. A compiler is allowed to assume the overflow never happens and to change the code based on that assumption.

The program below negates the smallest int32_t the plain way:

#include <cstdint>
#include <iostream>
#include <limits>
 
int main() {
    std::int32_t m = std::numeric_limits<std::int32_t>::min();
    std::int32_t neg = -m;
    std::cout << "-INT32_MIN = " << neg << "\n";
    return 0;
}

Output from a run with g++ -std=c++20 -Wall, and the same output with -O2:

-INT32_MIN = -2147483648

This machine printed the wrapped value, but the result is not promised. The program is wrong even when the output looks harmless, because the same code may print something else with another compiler or another optimisation level. A check like checked_abs below is the correct fix.

A harder example: absolute value

The absolute value of a number is its distance from zero: 42 for both 42 and -42. For most ints, the function is easy. For the smallest int, the answer would be 2147483648, which does not fit. The function below returns an empty optional for that single case.

#include <iostream>
#include <limits>
#include <optional>
 
std::optional<int> checked_abs(int x) {
    if (x == std::numeric_limits<int>::min()) {
        return std::nullopt;
    }
    return x < 0 ? -x : x;
}
 
void show(const std::optional<int>& value) {
    if (value) {
        std::cout << *value << "\n";
    } else {
        std::cout << "does not fit\n";
    }
}
 
int main() {
    show(checked_abs(-42));
    show(checked_abs(std::numeric_limits<int>::min()));
    return 0;
}

Output from a run:

42
does not fit

The function tests for the one value that cannot be negated before it negates anything. The rest of the code can then use plain -x, because the only input that would overflow has already been handled.

Common mistakes

Assuming that a value stored in a small type keeps its value. The compiler does not always warn you. The program below stores 200 in an int8_t:

#include <cstdint>
#include <iostream>
 
int main() {
    std::int8_t x = 200;
    std::cout << static_cast<int>(x) << "\n";
    return 0;
}

Output with g++ -std=c++20 -Wall: no warning, and the program prints:

-56

The value 200 is 256 - 56. In 8 bits, 200 and -56 have the same pattern, so the value is stored as -56. Check the range of the type before you store a constant that might be too big for it.

Overflow that the compiler can see. Sometimes the compiler spots an overflow while it compiles. The line below adds 1 to the largest int32_t:

std::int32_t y = std::numeric_limits<std::int32_t>::max() + 1;

Compiling with g++ -std=c++20 -Wall gives this warning:

warning: integer overflow in expression of type 'int' results in '-2147483648' [-Woverflow]

The compiler still produces a program, so the warning is the only sign of the problem. Treat warnings as errors when you write code for real use.

Calling std::abs on the smallest value. The result of std::abs(std::numeric_limits<int>::min()) is undefined behaviour for the same reason as -m above. Use a function like checked_abs when the input can be the smallest value.

Comparing signed and unsigned values. A signed int and an unsigned unsigned int are compared as unsigned when they are mixed. The code below looks like it should print "true", because -1 is less than 0:

#include <iostream>
 
int main() {
    int negative = -1;
    unsigned int u = 0;
    if (negative < u) {
        std::cout << "-1 < 0u is true\n";
    } else {
        std::cout << "-1 < 0u is false\n";
    }
    return 0;
}

Compiling with g++ -std=c++20 -Wall gives this warning, and the program prints -1 < 0u is false:

warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]

The value -1 is converted to the unsigned value 4294967295 before the comparison, which is larger than 0. The fix is to choose one type for both values, or to check the sign first.

Practice

Exercise 1. What are the smallest and largest values of uint16_t? Use the formula, then check your answer with std::numeric_limits.

Show the answer

The smallest value is 0 and the largest is 65535. The formula gives 2 to the power 16, minus 1, which is 65535.

Exercise 2. What are the 8-bit patterns for -1 and for -2 in int8_t?

Show the answer

-1 is 11111111 and -2 is 11111110. For -2, the value is -128 + 126 = -2.

Exercise 3. Write a function bool fits_in_int8(int x) that returns true when x is between -128 and 127 inclusive. Use std::numeric_limits so the numbers are not written by hand. Test it with 127, 128, -128 and -129.

Show the answer

#include <cstdint>
#include <iostream>
#include <limits>
 
bool fits_in_int8(int x) {
    return x >= std::numeric_limits<std::int8_t>::min() && x <= std::numeric_limits<std::int8_t>::max();
}
 
int main() {
    std::cout << "fits 127: " << fits_in_int8(127) << " fits 128: " << fits_in_int8(128)
              << " fits -128: " << fits_in_int8(-128) << " fits -129: " << fits_in_int8(-129) << "\n";
    return 0;
}

Output: fits 127: 1 fits 128: 0 fits -128: 1 fits -129: 0. The 1 means true and the 0 means false, because bool values are printed as numbers by default.

Exercise 4. The bit pattern 11110000 is read as an int8_t. What number is it? Work it out by hand, then check with a program that converts the pattern with static_cast<std::int8_t>(0b11110000).

Show the answer

It is -16. The sign bit gives -128, and the other bits give 64 + 32 + 16 = 112. The sum is -128 + 112 = -16. A program that prints the converted value shows -16.

Exercise 5. Why does -x for x = -128 in int8_t give -128 and not 128?

Show the answer

The value 128 does not fit in an int8_t, whose largest value is 127. Two's complement negation (flip the bits, add 1) returns the same bit pattern, which reads as -128.

Summary

• Each integer type has a fixed number of bits, so it can hold only a fixed set of values.
• For an unsigned type with n bits, the range is 0 to 2 to the power n, minus 1. For a signed type, it is -(2 to the power n-1) to 2 to the power n-1, minus 1.
• Read the exact limits with std::numeric_limits<T>::min() and max() from <limits>.
• The negative side has one more value than the positive side, so the negation of the smallest signed value does not fit and wraps back to itself.
• Signed overflow is undefined behaviour in C++, so check the limits before you add, subtract, or negate values that might reach them.