Integer types and overflow

An integer type fixes the range of numbers a variable can hold: int up to about 2 \cdot 10^9, long long up to about 9 \cdot 10^{18}. A result outside the range overflows: the program prints a wrong number with no error, so a solution must use a type wide enough for every value it computes. If a value can pass about 1.8 \cdot 10^{19}, no built-in type holds it; use big integers.

Explanation

A made-up type holds only the 16 numbers from −8 to 7. Start at 5 and add 1 four times: 6, 7, −8, −7. Adding 1 to the largest number gives the smallest one: the value wraps around.

Fig. 1. From 7, adding 1 lands on −8.

A result past the end of the range is an overflow.

A rectangle has sides a = 100000 and b = 100000, both read into int variables. Its area is 10^{10}, more than int can hold: the largest int is 2147483647. The line int area = a * b; prints 1410065408. The number isn't even negative.

The obvious fix is to declare area as long long.

The type of an operation is the type of its operands, so int * int is done in int, whatever variable receives the result. In the red row of the figure below, the product is already wrong when it reaches area.

Fig. 2. The value goes wrong in the product cell; area only stores it.

So widen first: make the multiplication itself run in long long. When the operands have different types, C++ converts the narrower one to the wider type first. Write long long area = 1LL * a * b;: 1LL is the number 1 as a long long, so 1LL * a is a long long, and so is the product with b (the blue row). The cast (long long)a converts a to long long in the same way. Or read a and b into long long variables from the start. Both print 10000000000. Reading into long long also matters for big inputs: cin >> x into an int with input 10^{10} fails, x becomes 2147483647 and the stream stops reading.

Contest solutions mostly need two types:

Avoiding overflow in any solution takes three steps:

1. Estimate the largest value of every expression from the constraints, intermediate results included.

2. Choose the type from the table above.

3. Widen first, so that the operation itself runs in the wide type.

These estimates come up most often:

In C++

Sums

In a running sum from loops, the accumulator must be long long. The numbers may stay int, because sum + x is done in the wider type. With an int accumulator, three numbers of 10^9 give −1294967296.

long long sum = 0;                // estimate: up to n * 10^9, so choose long long
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    sum += x;
}

Products with a limit

Some problems multiply numbers until the result passes a limit of their own, such as "print overflow if the product is more than 10^{18}". With factors up to 2 \cdot 10^9, even long long can't hold the last product, so check first, before each multiplication. The check divides, p > LIMIT / x, because computing p * x to compare it would itself overflow. For the factors 10^9, 10^9, 2 \cdot 10^9:

Without the check, the last product would be 2 \cdot 10^{27}, far past LLONG_MAX.

const long long LIMIT = 1000000000000000000LL;   // 10^18
long long p = 1;
for (int i = 0; i < n; i++) {
    long long x = f[i];           // the factors, all positive
    if (p > LIMIT / x) {          // estimate: p * x would be more than LIMIT, so check first
        cout << "overflow";
        return 0;
    }
    p *= x;
}
cout << p;

This check assumes positive factors. A zero factor makes the product 0, so stop there before dividing by it.

Unsigned types

Unsigned types have no negative numbers, and for them wrapping around is defined: 0u - 1 is 4294967295. Use unsigned long long for answers between about 9.2 \cdot 10^{18} and 1.8 \cdot 10^{19}.

v.size() is unsigned. On an empty vector, v.size() - 1 is 18446744073709551615, not −1. Write i + 1 < v.size() instead of i < v.size() - 1, or convert the size to int first: (int)v.size() - 1.

A safe INF

Many solutions keep a value INF that means "no answer yet", such as the starting value of a minimum. Code such as best + cost adds to INF, so INF plus the largest value added must still fit in the type. For added values up to 10^9, use 1e9 for int; for values up to 10^{18}, use 1e18 for long long. With INF = INT_MAX, INF + 5 gives −2147483644. That is smaller than any real total, so it wins the minimum.

Finding an overflow

To find an overflow while testing, run the largest input the constraints allow. Compiling with -fsanitize=undefined makes the program report "signed integer overflow" with the line number when it happens.

Lines to copy

Write long long, not long: long has 64 bits on the Linux judge but 32 bits on Windows compilers.

#include <climits>                    // INT_MAX, LLONG_MAX
long long a, b;                       // read numbers that get multiplied as long long
long long p = 1LL * x * y;            // x, y are int: widen first
long long sum = 0;                    // a sum of many numbers
const long long INF = 1e18;           // INF + INF still fits
if (x > LLONG_MAX / y) { }            // x, y > 0: x * y would overflow, don't multiply

Common mistakes

• Checking if (a * b < 0) after multiplying. The product of 100000 and 100000 overflows to a positive number, and since signed overflow is undefined, the compiler may even remove the check. Check before multiplying.

• Using x > LLONG_MAX / y when a number can be negative. For x = −10 and y = 10^{18} the check passes, yet the product -10^{19} overflows. Check the absolute values instead.

Similar techniques

Modular arithmetic keeps only remainders when a problem asks for the answer modulo 10^9 + 7. The numbers stay small, but every product of two remainders still needs long long.

Big integers store a number with more than 19 digits, such as $21!$ or 2^{100}, digit by digit. GCC's __int128 reaches about 1.7 \cdot 10^{38}, but cin and cout can't read or print it.

Floating-point numbers such as double reach 10^{308} but keep only about 15–16 significant digits, so 2^{53} + 1 is already stored inexactly. Use them for fractions, not to avoid overflow.

Practice