Skip to content

CONCEPT Cited by 1 source

Integer overflow

Definition

Integer overflow is the condition in which the result of an arithmetic operation on fixed-width integer types falls outside the representable range of that type. For a signed 32-bit int the range is [−2^31, 2^31 − 1]; for unsigned 32-bit it is [0, 2^32 − 1]. When a sum, product, difference, or shift produces a value outside this range, the machine result is not the mathematical result.

The bit-level behaviour differs by language:

  • Java — signed arithmetic wraps around two's-complement. INT_MAX + 1 == INT_MIN. Defined by the JLS.
  • C / C++ (signed) — undefined behaviour per ISO/IEC 9899 §6.5 and the C++ standard. The compiler is allowed to assume signed overflow does not happen, and may emit code that produces any result (including deleting the surrounding code path).
  • C / C++ (unsigned) — defined modular arithmetic: UINT_MAX + 1 == 0.
  • Rust — debug builds panic on overflow; release builds wrap (two's-complement). Explicit APIs (wrapping_add, checked_add, saturating_add, overflowing_add) let the programmer opt in to specific semantics.
  • Go — signed overflow wraps silently.

The canonical bug: (low + high) / 2

The most cited instance — Joshua Bloch, 2006 — is the midpoint computation in binary search and mergesort:

int mid = (low + high) / 2;

For low, high within half the int range this is the average, truncated down — as Bentley's Programming Pearls describes. Once the array length reaches 2^30 (roughly one billion elements), low + high can exceed INT_MAX = 2^31 − 1, overflowing to a negative value; the signed division by 2 preserves the sign; a[mid] indexes at a negative offset and throws / corrupts.

Two decades of undetected existence — in Programming Pearls (1986 / 2000) and in java.util.Arrays.binarySearch (for ~9 years in the JDK) — because arrays that large didn't exist when the code was written. The bug didn't appear; the precondition did.

The fixes

Two idiomatic safe-midpoint shapes (see patterns/safe-midpoint-computation):

int mid = low + ((high - low) / 2);   // never forms the overflowing sum
int mid = (low + high) >>> 1;         // logical (unsigned) right shift — wrap is undone

In C / C++:

mid = ((unsigned int)low + (unsigned int)high) >> 1;

A 2008 update to Bloch's post (from Antoine Trux, Nokia Research) flagged that the original C form relied on signed overflow — which C99 §6.5 and the C++ standard leave undefined. The unsigned cast is the only form guaranteed-correct by the language spec.

Where integer overflow shows up

  • Divide-and-conquer midpoint computation — binary search, mergesort, quicksort partitioning, the while (low <= high) body of every classic algorithm. One shape, entire algorithm family.
  • Array-size arithmetic — malloc(n * sizeof(T)) overflowing size_t is a classic C/C++ vulnerability class (CVE-routine); a tiny n and a large sizeof(T) (or vice versa) produces a small allocation that the code then writes past.
  • Time arithmetic — 2038 time_t overflow; millisecond / nanosecond counters overflowing 32-bit; monotonic-clock rollovers.
  • Counter / sequence-number arithmetic — TCP sequence numbers, Lamport-clock monotonicity, database CSNs; wraparound has to be defended against by "modular comparison" (RFC 1982 Serial Number Arithmetic) rather than naive <.
  • Memory-allocator + offset math — length-prefixed buffers, negative-stride loops, size - 1 underflow.

Sibling / adjacent concepts

  • concepts/memory-safety — integer overflow is one substrate of C/C++ memory-safety bugs (undersized allocation → bounds error). Rust's type-level checked_add / wrapping_add / saturating_add is the language-level response.
  • concepts/unsigned-right-shift — Java's >>>; the language primitive that makes overflow recoverable for averaging operations (treats the bit pattern as unsigned, so the wrapped high-bit-set sum still shifts to the correct midpoint).
  • concepts/program-correctness — overflow is the paradigmatic example of "correct under the inputs we tested, wrong under inputs we didn't" — the gap exhaustive testing cannot close.
  • concepts/lightweight-formal-verification — executable-spec property tests are a direct response to arithmetic-overflow bugs that sit dormant for years because no hand-written test case hits them.

Seen in

Last updated · 200 distilled / 1,178 read