2.07Beginner8 topics16 min6 interactive animations

Numeric correctness in Java

Silent numeric bugs cause more wrong answers than logic errors: int overflow, Math.abs of the minimum value, signed shifts, negative modulo and floating-point equality. Each item here has a concrete failing input and the fix.

Learning goals

Predict and prevent int overflow
Compute midpoints and products safely
Use floorMod and shifts correctly
Compare floating-point values with a tolerance

Prerequisites

Java language essentialsArrays and types

2.07.1

int vs long

An int holds up to 2,147,483,647 (about 2.1 × 10⁹). Values such as sums of 10⁵ numbers each up to 10⁵, products of two 10⁵ values, or factorials above 12! no longer fit. Use long (up to about 9.2 × 10¹⁸) whenever an intermediate result may exceed 2³¹ - 1.

Pick the type for the largest intermediate value, not the largest input. Open the demo and try different operations.

Java

1int sumInt = 0; long sumLong = 0;
2for (int i = 0; i < 100_000; i++) { sumInt += i; sumLong += i; }
3// sumLong = 4999950000; sumInt wrapped around to 704982704
4long fact = 1; for (int i = 2; i <= 20; i++) fact *= i;   // 20! = 2432902008176640000 fits in long

32-bit int arithmetic and overflow

Interactive · edit the input

a = 2147483647

01111111bits 31-24

11111111bits 23-16

11111111bits 15-8

11111111bits 7-0

b = 1

00000000bits 31-24

00000000bits 23-16

00000000bits 15-8

00000001bits 7-0

Setup

A Java int is 32 bits in two's complement. Here are the operands as bit patterns; the top bit is the sign bit.

Step 1 / 3

Java

1int a = ..., b = ...;                    // 32-bit signed: -2147483648 .. 2147483647
2int sum = a + b;                         // wraps around silently on overflow
3long wide = (long) a + b;                // widen BEFORE the operation
4int prod = a * b;                        // wraps around silently on overflow
5long wideProd = (long) a * b;            // widen one operand first
6int unsafeMid = (lo + hi) / 2;           // lo + hi may overflow and turn negative
7int safeMid = lo + (hi - lo) / 2;        // hi - lo cannot overflow when 0 <= lo <= hi
8int abs = Math.abs(a);                   // Math.abs(Integer.MIN_VALUE) is still negative
9int arith = a >> b;                      // shifts in copies of the sign bit
10int logical = a >>> b;                   // shifts in zeros

Live state

2147483647

No condition evaluated on this step

Execution trace (dry run table)Show 3 steps

Step	Line	State	What happens
1	L1	a=2147483647 b=1	A Java int is 32 bits in two's complement. Here are the operands as bit patterns; the top bit is the sign bit.
2	L2	true result=2147483648 int range=[-2147483648, 2147483647]	The true result 2147483648 is outside the int range.
3	L2	return=-2147483648 overflow=true	Result: -2147483648. The bits wrapped around instead of raising an error, so the answer is wrong by 2^32 = 4294967296. Java never throws on int overflow (use Math.addExact or long to detect or avoid it).

2.07.2

Integer overflow

Java integer arithmetic wraps around silently modulo 2³²: Integer.MAX_VALUE + 1 is Integer.MIN_VALUE. No exception is thrown, so the program continues with a wrong value. Detect it with Math.addExact, subtractExact and multiplyExact (they throw ArithmeticException) or by computing in long.

Step through the demo's addition cases to see the wrapped results.

Java

1int x = Integer.MAX_VALUE;     // 2147483647
2int y = x + 1;                 // -2147483648
3try { Math.addExact(x, 1); } catch (ArithmeticException e) { System.out.println("overflow detected"); }
4boolean willOverflow = (long) x + 1 > Integer.MAX_VALUE;   // true

32-bit int arithmetic and overflow

Interactive · edit the input

a = 2147483647

01111111bits 31-24

11111111bits 23-16

11111111bits 15-8

11111111bits 7-0

b = 1

00000000bits 31-24

00000000bits 23-16

00000000bits 15-8

00000001bits 7-0

Setup

A Java int is 32 bits in two's complement. Here are the operands as bit patterns; the top bit is the sign bit.

Step 1 / 3

Java

1int a = ..., b = ...;                    // 32-bit signed: -2147483648 .. 2147483647
2int sum = a + b;                         // wraps around silently on overflow
3long wide = (long) a + b;                // widen BEFORE the operation
4int prod = a * b;                        // wraps around silently on overflow
5long wideProd = (long) a * b;            // widen one operand first
6int unsafeMid = (lo + hi) / 2;           // lo + hi may overflow and turn negative
7int safeMid = lo + (hi - lo) / 2;        // hi - lo cannot overflow when 0 <= lo <= hi
8int abs = Math.abs(a);                   // Math.abs(Integer.MIN_VALUE) is still negative
9int arith = a >> b;                      // shifts in copies of the sign bit
10int logical = a >>> b;                   // shifts in zeros

Live state

2147483647

No condition evaluated on this step

Execution trace (dry run table)Show 3 steps

Step	Line	State	What happens
1	L1	a=2147483647 b=1	A Java int is 32 bits in two's complement. Here are the operands as bit patterns; the top bit is the sign bit.
2	L2	true result=2147483648 int range=[-2147483648, 2147483647]	The true result 2147483648 is outside the int range.
3	L2	return=-2147483648 overflow=true	Result: -2147483648. The bits wrapped around instead of raising an error, so the answer is wrong by 2^32 = 4294967296. Java never throws on int overflow (use Math.addExact or long to detect or avoid it).

2.07.3

Safe midpoint

(lo + hi) / 2 overflows when lo + hi exceeds 2³¹ - 1. With lo = 1_500_000_000 and hi = 2_000_000_000 the sum wraps to -794,967,296 and the midpoint becomes -397,483,648, a negative index. The safe forms are lo + (hi - lo) / 2 or (lo + hi) >>> 1.

This bug lived in the JDK's own binary search for years. Always use the safe form.

Java

1int lo = 1_500_000_000, hi = 2_000_000_000;
2int bad  = (lo + hi) / 2;          // -397483648
3int good = lo + (hi - lo) / 2;     // 1750000000
4int also = (lo + hi) >>> 1;        // 1750000000 (unsigned shift treats the wrapped sum as unsigned)

32-bit int arithmetic and overflow

Interactive · edit the input

a = 2147483647

01111111bits 31-24

11111111bits 23-16

11111111bits 15-8

11111111bits 7-0

b = 1

00000000bits 31-24

00000000bits 23-16

00000000bits 15-8

00000001bits 7-0

Setup

A Java int is 32 bits in two's complement. Here are the operands as bit patterns; the top bit is the sign bit.

Step 1 / 3

Java

1int a = ..., b = ...;                    // 32-bit signed: -2147483648 .. 2147483647
2int sum = a + b;                         // wraps around silently on overflow
3long wide = (long) a + b;                // widen BEFORE the operation
4int prod = a * b;                        // wraps around silently on overflow
5long wideProd = (long) a * b;            // widen one operand first
6int unsafeMid = (lo + hi) / 2;           // lo + hi may overflow and turn negative
7int safeMid = lo + (hi - lo) / 2;        // hi - lo cannot overflow when 0 <= lo <= hi
8int abs = Math.abs(a);                   // Math.abs(Integer.MIN_VALUE) is still negative
9int arith = a >> b;                      // shifts in copies of the sign bit
10int logical = a >>> b;                   // shifts in zeros

Live state

2147483647

No condition evaluated on this step

Execution trace (dry run table)Show 3 steps

Step	Line	State	What happens
1	L1	a=2147483647 b=1	A Java int is 32 bits in two's complement. Here are the operands as bit patterns; the top bit is the sign bit.
2	L2	true result=2147483648 int range=[-2147483648, 2147483647]	The true result 2147483648 is outside the int range.
3	L2	return=-2147483648 overflow=true	Result: -2147483648. The bits wrapped around instead of raising an error, so the answer is wrong by 2^32 = 4294967296. Java never throws on int overflow (use Math.addExact or long to detect or avoid it).

2.07.4

long multiplication

Multiplying two ints gives an int, and it overflows before any widening to long happens. long p = a * b; is wrong for large ints. Cast one operand first: long p = (long) a * b;.

For modular arithmetic, reduce after every multiplication and make sure the product of two reduced values fits in long. With modulus 10⁹ + 7 the product is below 10¹⁸ + 10¹⁰, which fits.

Java

1int a = 100_000, b = 100_000;
2long wrong = a * b;            // 1410065408 (int multiplication, then widened)
3long right = (long) a * b;     // 10000000000
4final int MOD = 1_000_000_007;
5long r = ((long) 123_456_789 * 987_654_321) % MOD;

32-bit int arithmetic and overflow

Interactive · edit the input

a = 2147483647

01111111bits 31-24

11111111bits 23-16

11111111bits 15-8

11111111bits 7-0

b = 1

00000000bits 31-24

00000000bits 23-16

00000000bits 15-8

00000001bits 7-0

Setup

A Java int is 32 bits in two's complement. Here are the operands as bit patterns; the top bit is the sign bit.

Step 1 / 3

Java

1int a = ..., b = ...;                    // 32-bit signed: -2147483648 .. 2147483647
2int sum = a + b;                         // wraps around silently on overflow
3long wide = (long) a + b;                // widen BEFORE the operation
4int prod = a * b;                        // wraps around silently on overflow
5long wideProd = (long) a * b;            // widen one operand first
6int unsafeMid = (lo + hi) / 2;           // lo + hi may overflow and turn negative
7int safeMid = lo + (hi - lo) / 2;        // hi - lo cannot overflow when 0 <= lo <= hi
8int abs = Math.abs(a);                   // Math.abs(Integer.MIN_VALUE) is still negative
9int arith = a >> b;                      // shifts in copies of the sign bit
10int logical = a >>> b;                   // shifts in zeros

Live state

2147483647

No condition evaluated on this step

Execution trace (dry run table)Show 3 steps

Step	Line	State	What happens
1	L1	a=2147483647 b=1	A Java int is 32 bits in two's complement. Here are the operands as bit patterns; the top bit is the sign bit.
2	L2	true result=2147483648 int range=[-2147483648, 2147483647]	The true result 2147483648 is outside the int range.
3	L2	return=-2147483648 overflow=true	Result: -2147483648. The bits wrapped around instead of raising an error, so the answer is wrong by 2^32 = 4294967296. Java never throws on int overflow (use Math.addExact or long to detect or avoid it).

2.07.5

Math.abs corner case

Math.abs(Integer.MIN_VALUE) returns Integer.MIN_VALUE (still negative) because +2,147,483,648 does not fit in an int. The same applies to Long.MIN_VALUE, and -x and Math.abs on a hash code can produce a negative array index.

Use Math.floorMod(hash, n) for bucket indexes, and use long when you must take absolute values of arbitrary ints.

Java

1int a = Math.abs(Integer.MIN_VALUE);          // -2147483648
2long b = Math.abs((long) Integer.MIN_VALUE);  // 2147483648
3int bucket = Math.floorMod("polygenelubricants".hashCode(), 16);   // always 0..15

32-bit int arithmetic and overflow

Interactive · edit the input

a = 2147483647

01111111bits 31-24

11111111bits 23-16

11111111bits 15-8

11111111bits 7-0

b = 1

00000000bits 31-24

00000000bits 23-16

00000000bits 15-8

00000001bits 7-0

Setup

A Java int is 32 bits in two's complement. Here are the operands as bit patterns; the top bit is the sign bit.

Step 1 / 3

Java

1int a = ..., b = ...;                    // 32-bit signed: -2147483648 .. 2147483647
2int sum = a + b;                         // wraps around silently on overflow
3long wide = (long) a + b;                // widen BEFORE the operation
4int prod = a * b;                        // wraps around silently on overflow
5long wideProd = (long) a * b;            // widen one operand first
6int unsafeMid = (lo + hi) / 2;           // lo + hi may overflow and turn negative
7int safeMid = lo + (hi - lo) / 2;        // hi - lo cannot overflow when 0 <= lo <= hi
8int abs = Math.abs(a);                   // Math.abs(Integer.MIN_VALUE) is still negative
9int arith = a >> b;                      // shifts in copies of the sign bit
10int logical = a >>> b;                   // shifts in zeros

Live state

2147483647

No condition evaluated on this step

Execution trace (dry run table)Show 3 steps

Step	Line	State	What happens
1	L1	a=2147483647 b=1	A Java int is 32 bits in two's complement. Here are the operands as bit patterns; the top bit is the sign bit.
2	L2	true result=2147483648 int range=[-2147483648, 2147483647]	The true result 2147483648 is outside the int range.
3	L2	return=-2147483648 overflow=true	Result: -2147483648. The bits wrapped around instead of raising an error, so the answer is wrong by 2^32 = 4294967296. Java never throws on int overflow (use Math.addExact or long to detect or avoid it).

2.07.6

Signed shifts

x << k shifts left, filling with zeros (multiplying by 2ᵏ unless it overflows). x >> k is an arithmetic shift: it copies the sign bit, so negative values stay negative and the result rounds toward negative infinity. x >>> k is a logical shift that fills with zeros, treating the 32 bits as unsigned.

-8 >> 1 is -4, but -8 >>> 1 is 2147483644. For ints the shift distance is taken modulo 32, so 1 << 32 equals 1.

Java

1int a = -8 >> 1;        // -4
2int b = -8 >>> 1;       // 2147483644
3int c = 1 << 31;        // -2147483648
4int d = 1 << 32;        // 1 (shift distance 32 % 32 = 0)
5int half = -7 >> 1;     // -4: floors; -7 / 2 is -3 (truncates)

32-bit int arithmetic and overflow

Interactive · edit the input

a = 2147483647

01111111bits 31-24

11111111bits 23-16

11111111bits 15-8

11111111bits 7-0

b = 1

00000000bits 31-24

00000000bits 23-16

00000000bits 15-8

00000001bits 7-0

Setup

A Java int is 32 bits in two's complement. Here are the operands as bit patterns; the top bit is the sign bit.

Step 1 / 3

Java

1int a = ..., b = ...;                    // 32-bit signed: -2147483648 .. 2147483647
2int sum = a + b;                         // wraps around silently on overflow
3long wide = (long) a + b;                // widen BEFORE the operation
4int prod = a * b;                        // wraps around silently on overflow
5long wideProd = (long) a * b;            // widen one operand first
6int unsafeMid = (lo + hi) / 2;           // lo + hi may overflow and turn negative
7int safeMid = lo + (hi - lo) / 2;        // hi - lo cannot overflow when 0 <= lo <= hi
8int abs = Math.abs(a);                   // Math.abs(Integer.MIN_VALUE) is still negative
9int arith = a >> b;                      // shifts in copies of the sign bit
10int logical = a >>> b;                   // shifts in zeros

Live state

2147483647

No condition evaluated on this step

Execution trace (dry run table)Show 3 steps

Step	Line	State	What happens
1	L1	a=2147483647 b=1	A Java int is 32 bits in two's complement. Here are the operands as bit patterns; the top bit is the sign bit.
2	L2	true result=2147483648 int range=[-2147483648, 2147483647]	The true result 2147483648 is outside the int range.
3	L2	return=-2147483648 overflow=true	Result: -2147483648. The bits wrapped around instead of raising an error, so the answer is wrong by 2^32 = 4294967296. Java never throws on int overflow (use Math.addExact or long to detect or avoid it).

2.07.7

Modulo sign

In Java % takes the sign of the dividend, so -7 % 3 is -1, and integer division truncates toward zero, so -7 / 3 is -2. For a non-negative remainder use Math.floorMod, and Math.floorDiv for the matching quotient (-3 here).

A common idiom for modular subtraction is ((a - b) % m + m) % m, or Math.floorMod(a - b, m).

Java

1int r1 = -7 % 3;                  // -1
2int r2 = Math.floorMod(-7, 3);    // 2
3int q1 = -7 / 3;                  // -2
4int q2 = Math.floorDiv(-7, 3);    // -3
5int wrapIndex = Math.floorMod(0 - 1, 5);   // 4: circular previous index

2.07.8

Floating-point comparisons

double stores binary approximations: 0.1 + 0.2 is 0.30000000000000004, so 0.1 + 0.2 == 0.3 is false. Compare with a tolerance, Math.abs(a - b) < 1e-9, or avoid floating point by using integers (cents instead of dollars) or BigDecimal.

Beyond 2⁵³ double cannot represent every integer, so never use it for exact integer arithmetic on large values.

Java

1double s = 0.1 + 0.2;
2boolean eq = s == 0.3;                      // false
3boolean close = Math.abs(s - 0.3) < 1e-9;   // true
4long cents = 10 + 20;                        // exact: 30
5int cmp = Double.compare(0.1 + 0.2, 0.3);    // 1

Practice ladder

Now try it yourself

Easy

Predict Integer.MAX_VALUE + 1 and Math.abs(Integer.MIN_VALUE)
Compute -17 % 5 and Math.floorMod(-17, 5)

Medium

Fix long p = a * b for int a and b
Why can (lo + hi) / 2 fail in a binary search over a 2 × 10⁹ range? Give numbers

Advanced

Write a method that adds two ints and returns Integer.MAX_VALUE or MIN_VALUE on overflow (saturating addition) without using long

Key takeaways

Overflow wraps silently: widen to long before the operation, not after.
Use lo + (hi - lo) / 2 and Math.floorMod; avoid Math.abs on arbitrary ints.
Use tolerances or integers instead of == on doubles.