Pointer Walk

Integer Overflow

Math.abs() returned a negative number. What happens when a value does not fit in 32 bits.

Languages and RuntimesBeginner7 min read

Numbers have a size

On paper a number can be as long as you like. In most programming languages an integer is stored in a fixed number of bits, and that sets a hard limit on how large it can be.

TypeBitsSmallestLargest
8-bit signed8-128127
16-bit signed16-32,76832,767
32-bit signed (int in Java and C)32-2,147,483,6482,147,483,647
64-bit signed (long)64about -9.2 quintillionabout 9.2 quintillion

What happens when a calculation goes past the largest value?

It wraps around

A car's odometer with six digits, sitting at 999,999, does not show 1,000,000 after one more mile. It shows 000,000. The extra digit has nowhere to go.

Integers do the same. This is integer overflow. The animation uses 8 bits so the whole thing fits on screen. A 32-bit int behaves identically, with more digits.

Counting past the largest 8-bit numberInteractive
sign0
641
321
161
81
41
20
10

Start. A signed 8-bit integer: eight bits, which can show 256 different patterns. They are shared out as -128 to 127. The leftmost bit marks negative numbers.

The bits, read as a number
124
Largest possible
127
Smallest possible
-128

127 plus 1 is -128. The largest value is followed by the smallest.

Why negative numbers are lopsided

Eight bits make 256 patterns. One of them is zero. That leaves 255 for everything else, an odd number, so it cannot be split evenly between positive and negative.

The system all modern computers use, two's complement, gives the spare pattern to the negative side: 128 negative values, zero, and 127 positive values.

So there is one number with no positive partner. In 8 bits it is -128. In 32 bits it is -2,147,483,648.

Math.abs() returned a negative number

Here is the consequence.

Math.abs() returning a negative numberInteractive
1int smallest = Integer.MIN_VALUE;
2int result = Math.abs(smallest);
3System.out.println(result);

Variables

nothing yet

Start. A Java int has 32 bits. Its range is -2,147,483,648 to 2,147,483,647.

Math.abs is supposed to return a number with the sign removed. For this one input, the correct answer does not fit in an int. So the result overflows, and lands exactly back where it started.

It is one value out of four billion. That is precisely why it survives testing and turns up in production, for example when code takes abs of a hash value to pick a bucket and now and then gets a negative index.

Famous overflows

  • A video passed 2,147,483,647 views and the site's 32-bit counter could go no higher. The counter was widened to 64 bits.
  • The year 2038. Many systems count time as seconds since 1970 in a signed 32-bit integer. That count overflows on 19 January 2038.
  • Binary search. The textbook (lo + hi) / 2 overflows for very large arrays. See Binary Search.
  • A rocket was lost in 1996 when a number was converted into a 16-bit integer too small to hold it.

Defending against it

  1. Pick a type that is big enough

    For counts, money in the smallest unit, ids and timestamps, use 64 bits.

  2. Use checked arithmetic where it matters

    Many languages offer operations that raise an error on overflow instead of wrapping. In Java, Math.addExact(a, b) throws an exception.

  3. Rearrange calculations to stay small

    lo + (hi - lo) / 2 never forms the large sum that (lo + hi) / 2 does.

  4. Remember the one asymmetric value

    Negating or taking abs of the smallest integer does not work.

Key takeaways

  • Most languages store integers in a fixed number of bits, which limits their range.
  • Going past the largest value wraps around to the smallest, usually with no error.
  • The range is lopsided: there is one more negative value than positive.
  • So abs() and negation fail for the smallest integer, returning it unchanged.
  • Use wide enough types, checked arithmetic where it matters, and calculations that stay small.

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    6 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress