Integer Ranges and Overflow

New words in this topic, in plain English. Come back here whenever one feels fuzzy.

Overflow

When a calculation's true result is too big (or too negative) to fit in the type, so the stored result is wrong.

Wrap around

Going past one end of the range and coming back at the other end, like a clock going from 12 to 1.

Binary

Writing numbers with only the digits 0 and 1. Each position is worth double the one to its right: 1, 2, 4, 8, 16, ...

Two's complement

The way Java (and almost every CPU) stores negative whole numbers: flip every bit of the positive number and add 1.

Sign bit

The leftmost bit of a signed integer. 1 means the number is negative.

Widening

Converting a value to a type with more bits, like int to long. It never loses information.

Exception

An error signal thrown while a program runs. If nothing catches it, the program stops and prints what went wrong. Phase 7 covers them.

BigInteger

A class in java.math that stores whole numbers of any size, growing its memory as needed.

1. 1

   Find where factorials break

   Write int f = 1; and multiply it by 2, 3, 4, ... printing each result. Predict where the numbers stop making sense (hint: 13! is 6,227,020,800). Then switch f to long and see how far you get (20! is the last one that fits).

2. 2

   Swap in multiplyExact

   In the 'famous bugs' example replace 24 * 60 * 60 * 1000 * 1000 with nested Math.multiplyExact calls. Instead of a silently wrong number, you get an exception that points at the line.

3. 3

   Predict the byte

   Before running, predict what byte b = (byte) 200; prints. Then run it. (200 is 11001000 in binary; with the top bit worth -128 that's -128 + 72 = -56.)

Errors are the best teachers. Make each change, read the error, guess what went wrong, then reveal the answer.

public class Main {
    public static void main(String[] args) {
        int bytesPerUser = 50_000;
        int users = 100_000;
        int total = Math.multiplyExact(bytesPerUser, users);
        System.out.println(total);
    }
}

1. 1

   Java stores signed integers in two's complement. The top bit is the sign bit: 0 means zero or positive, 1 means negative. For a byte, 01111111 is 127 and adding 1 gives 10000000, which two's complement reads as -128.

2. 2

   Overflow is silent. Java's +, -, * on int and long never throw an exception and never print a warning; the extra high bits are simply discarded. The result is wrong but looks like a normal number.

3. 3

   The classic trap is **multiplying in int before widening**: long micros = 24 * 60 * 60 * 1000 * 1000; overflows in int arithmetic first and only then converts the wrong result to long. Make the first operand a long (24L * ...) so the whole calculation happens in 64 bits.

4. 4

   The range is lopsided: int goes from -2,147,483,648 to 2,147,483,647, so the most negative number has no positive partner. Math.abs(Integer.MIN_VALUE) and -Integer.MIN_VALUE both return Integer.MIN_VALUE, still negative.

5. 5

   To detect overflow use the exact methods added in Java 8: Math.addExact, subtractExact, multiplyExact, incrementExact, negateExact and toIntExact. They throw ArithmeticException: integer overflow instead of wrapping. To avoid it, use a wider type (long) or java.math.BigInteger, which has no size limit.

6. 6

   Overflow causes real bugs: the famous binary search bug mid = (low + high) / 2 sat in the JDK's own Arrays.binarySearch for nine years until 2006. The fix, low + (high - low) / 2 or (low + high) >>> 1, appears in the DSA course (/dsa) binary search module.

• ↔

  Wrapping arithmetic is the fastest possible and is exactly what hashing and checksums want, but it turns business-logic mistakes into silently wrong numbers.

• ↔

  Math.*Exact costs almost nothing and turns silent corruption into a loud failure; the trade is that you must decide what to do when it throws.

• ↔

  BigInteger can never overflow but is far slower and allocates an object per operation; use it only when values truly exceed long.

• I can explain two's complement and convert a small negative number to binary.

• I can predict the result of Integer.MAX_VALUE + 1 and Math.abs(Integer.MIN_VALUE).

• I spot the 'multiply in int, store in long' bug and fix it with an L.

• I can use Math.addExact, multiplyExact and toIntExact to detect overflow.

• I can write an overflow-safe binary search midpoint.