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.
| Type | Bits | Smallest | Largest |
|---|---|---|---|
| 8-bit signed | 8 | -128 | 127 |
| 16-bit signed | 16 | -32,768 | 32,767 |
32-bit signed (int in Java and C) | 32 | -2,147,483,648 | 2,147,483,647 |
64-bit signed (long) | 64 | about -9.2 quintillion | about 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.
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.
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) / 2overflows 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
Pick a type that is big enough
For counts, money in the smallest unit, ids and timestamps, use 64 bits.
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.Rearrange calculations to stay small
lo + (hi - lo) / 2never forms the large sum that(lo + hi) / 2does.Remember the one asymmetric value
Negating or taking
absof 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.