A. Programming Concepts and Skills · Data Types, Files and ExpressionsLimits of Finite Representation: Integer Bounds and Overflow
A1.4 A1.1About 70 minutes
Learning goals- I can state the range of an n-bit unsigned and signed (two's complement) integer.
- I can convert between negative integers and their two's complement bit patterns.
- I can explain and simulate integer overflow, and explain why Python's
int behaves differently from Java's int. - I can design algorithms that avoid overflow by choosing types, checking bounds or restructuring calculations.
Words to know
fixed-width integer
An integer stored in a set number of bits (8, 16, 32 or 64), so it has a smallest and largest possible value.
unsigned integer
An n-bit integer with no sign: range 0 to 2ⁿ − 1.
two's complement
The usual way to store signed integers: the top bit has weight −2ⁿ⁻¹. Range −2ⁿ⁻¹ to 2ⁿ⁻¹ − 1.
integer overflow
When a result is too big (or too small) for its type. Fixed-width integers usually wrap around silently.
arbitrary-precision integer
An integer that grows to use as much memory as it needs, like Python's int or Java's BigInteger.
sign bit
The leftmost bit of a two's complement number: 0 for zero or positive, 1 for negative.
Computers are finite
A computer's memory is huge, but every number inside it is stored in a fixed number of bits. In ICS3U you learned that 8 bits can make 2⁸ = 256 different patterns. That means an 8-bit number can only represent 256 different values. Ask it to store the 257th and something has to give.
This lesson is about what gives. You will see how negative integers are stored, what happens when a value goes past the limit (overflow), and how professional programmers design algorithms that never hit the wall. Python hides much of this from you, which is exactly why you need to understand it: the moment your data goes into a file, a database, a Java program or a graphics card, the limits come back.
Unsigned and signed ranges
With n bits there are 2ⁿ patterns.
- Unsigned (no negatives): 0 to 2ⁿ − 1. With 8 bits, 0 to 255 (one colour channel of a pixel).
- Signed, using two's complement: half the patterns are negative. The range is −2ⁿ⁻¹ to 2ⁿ⁻¹ − 1. With 8 bits, −128 to 127.
There is one more negative value than positive, because zero uses one of the "non-negative" patterns.
for bits in [8, 16, 32, 64]:
lo = -2 ** (bits - 1)
hi = 2 ** (bits - 1) - 1
print(f"{bits}-bit signed: {lo:,} to {hi:,}")
Integer bounds for common sizes. Java's byte, short, int and long are exactly these four ranges. :, adds thousands separators. Output, line by line: 8-bit signed: -128 to 127 | 16-bit signed: -32,768 to 32,767 | 32-bit signed: -2,147,483,648 to 2,147,483,647 | 64-bit signed: -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807
How two's complement works
The leftmost bit gets a negative weight. For 8 bits the weights are −128, 64, 32, 16, 8, 4, 2, 1.
- If the first bit is 0, the number is read as ordinary binary.
- If it is 1, start at −128 and add the other weights.
To negate a number: invert every bit, then add 1. The same adder circuit can then handle positive and negative numbers, which is why nearly all modern processors use this system.
10010110 is −128 + 16 + 4 + 2 = −106. Every other bit works like ordinary binary from ICS3U.Worked exampleExample 1: Convert to and from two's complement by hand
(a) Write −45 as an 8-bit two's complement pattern. (b) What value does the 8-bit pattern 11111011 represent?
- (a) Start with +45 in binary: 45 = 32 + 8 + 4 + 1 →
00101101. - Invert every bit:
11010010. Add 1: 11010011. So −45 is 11010011. - Check with weights: −128 + 64 + 16 + 2 + 1 = −45. ✓ (Or in Python:
format(-45 & 0xFF, "08b").) - (b) The leftmost bit is 1, so it is negative. Weights: −128 + 64 + 32 + 16 + 8 + 2 + 1 = −5.
- Or: invert
11111011 → 00000100, add 1 → 00000101 = 5, so the value is −5.
Overflow: wrapping around
What is 127 + 1 in an 8-bit signed integer? The true answer, 128, has no pattern. The hardware simply produces the pattern 10000000, which means −128. The value wraps around, like a car odometer rolling over, and usually no error is reported.
In Java, Integer.MAX_VALUE + 1 equals Integer.MIN_VALUE. In C and C++, signed overflow is officially undefined behaviour, which is even worse. Python's int never overflows, because it automatically uses more memory as the number grows.
0111), wraps around to the smallest, −8 (1000). Real 32-bit and 64-bit integers behave the same way, just with far more positions.def wrap(x, bits):
"""Return x the way a signed two's-complement integer of the given width would store it."""
half = 2 ** (bits - 1)
return (x + half) % 2 ** bits - half
print(wrap(127 + 1, 8), wrap(-128 - 1, 8), wrap(100 * 3, 8))
print(wrap(2_147_483_647 + 1, 32))
print(format(-106 & 0xFF, "08b"))
Simulating fixed-width overflow with % from Lesson 1. 127 + 1 in a signed byte becomes −128, just like Java's (byte) 128. & 0xFF shows the 8-bit pattern of a negative number. Output, line by line: -128 127 44 | -2147483648 | 10010110
Overflow is mod 2ⁿ
Fixed-width arithmetic is really arithmetic modulo 2ⁿ (Lesson 1). The wrap function shifts the range so that % lands in −2ⁿ⁻¹ to 2ⁿ⁻¹ − 1. Thinking of it this way lets you predict any overflow result quickly: 100 × 3 = 300, and 300 − 256 = 44.
import struct
values = [2_000_000_000, 3_000_000_000]
for v in values:
try:
data = struct.pack("<i", v) # 4-byte signed int, as in a binary file
print(v, "fits:", data.hex())
except struct.error:
print(v, "does not fit in a 32-bit signed int")
big = 2 ** 100
print(big, big.bit_length())
Python's own int has no fixed bound (2¹⁰⁰ is fine), but the moment you store an integer in a fixed-size format, such as a binary file (Lesson 12), a database column or a Java program, the bounds come back. Output, line by line: 2000000000 fits: 00943577 | 3000000000 does not fit in a 32-bit signed int | 1267650600228229401496703205376 101
When overflow really mattered
- Ariane 5 (1996): the first launch of this European rocket failed about 40 seconds after lift-off. Software converted a 64-bit floating-point value into a 16-bit signed integer; the value was too large, the conversion failed, and the inertial reference system that the guidance depended on shut down. The rocket carried no crew. The code had been reused from Ariane 4, whose slower flight path never produced such large values.
- The Year 2038 problem: many systems store time as a signed 32-bit count of seconds since 00:00:00 UTC on 1 January 1970. That count reaches 2,147,483,647 at 03:14:07 UTC on 19 January 2038, and the next second wraps to a date in 1901. Modern systems are moving to 64-bit time.
- Binary search: for years, many library versions of binary search computed the middle index as
(low + high) / 2 in Java, which overflows for arrays with more than about a billion elements. The fix is low + (high - low) / 2. You will meet binary search in the sibling unit Algorithm Design and Analysis.
Worked exampleExample 2: Designing around the bound
A Java method stores the total number of seconds a game server has been running in an int, adding 1 every second. How long until it overflows, and what are three ways to fix the design?
- The largest
int is 2,147,483,647. That many seconds is 2,147,483,647 ÷ 86,400 ≈ 24,855 days, or about 68 years. (Use divmod for exact days.) - That sounds safe, but the same counter in milliseconds overflows after about 24.9 days. Programs that run for weeks do hit that.
- Fix 1: use a wider type (
long, 64-bit), which lasts about 292 billion years in seconds (about 292 million years even in milliseconds). - Fix 2: check before adding:
if total > Integer.MAX_VALUE - step then handle it, or use Java's Math.addExact, which throws an exception instead of wrapping silently. - Fix 3: store a start time and compute the difference only when needed, so nothing keeps growing.
About 68 years for seconds (about 24.9 days for milliseconds). Choose a wider type, check before adding, or redesign.
Just for funA funny-but-true fact: in December 2014 YouTube said a music video's view count was getting close to 2,147,483,647, the largest 32-bit signed integer. They upgraded the counter to 64 bits, which allows about 9.2 quintillion views. That video has a long way to go.
Hands-on activityOdometer overflow
You need: paper, a pencil, and Python. If you have a car with a trip odometer, or a kitchen timer with digits, look at it too.
- Draw a 3-digit decimal "odometer" showing 998. Count up by 1 three times. What does it show after 999? That is unsigned overflow in base 10.
- Draw the 4-bit wheel from this lesson from memory and label every bit pattern with its signed value.
- Use
wrap(x, 8) to predict, then check, the 8-bit results of: 120 + 10, −100 − 50, 64 × 4, and 200 (stored directly). - Write one sentence for each: who might be affected if a bank, a game score, or a time stamp overflowed?
What to look for: the odometer shows 000 after 999; results −126, 106, 0 and −56; and a sensible sentence for each scenario.
Your turn
1What is the range of a 16-bit unsigned integer? Of a 16-bit signed integer?
Unsigned: 0 to 65,535. Signed: −32,768 to 32,767.
2Write −1 as an 8-bit two's complement pattern.
11111111. (+1 is 00000001; invert → 11111110; add 1 → 11111111.)
3What value is the 8-bit signed pattern 10000001?
4Use wrap from this lesson: what is wrap(130, 8)?
130 + 128 = 258; 258 % 256 = 2; 2 − 128 = −126.
5In Java, what is Integer.MAX_VALUE + 1?
−2,147,483,648 (Integer.MIN_VALUE): it wraps around.
6Why does 2 ** 200 work fine in Python but not in a Java long?
Python's int is arbitrary precision and grows as needed. A Java long has exactly 64 bits, so its largest value is about 9.2 × 10¹⁸, far less than 2²⁰⁰.
7How many seconds after the start of 1970 does a signed 32-bit time counter overflow?
After 2,147,483,647 seconds (2³¹ − 1), which is 03:14:07 UTC on 19 January 2038.
More practice: warm-up
1How many patterns can 10 bits make?
2What is the largest 8-bit unsigned value?
3What is the smallest 8-bit signed value?
4In two's complement, what does a first bit of 1 mean?
5Does Python's built-in int overflow?
No. It grows to any size memory allows.
More practice: on your own
1Convert −90 to 8-bit two's complement and check with weights.
90 = 64 + 16 + 8 + 2 = 01011010. Invert → 10100101, add 1 → 10100110. Check: −128 + 32 + 4 + 2 = −90. ✓
2A program multiplies two int values in Java: 50,000 × 50,000. What goes wrong, and what is the true answer?
The true answer is 2,500,000,000, which is larger than 2,147,483,647, so it overflows. Java gives 2,500,000,000 − 2³² = −1,794,967,296. Fix: use long (50_000L * 50_000).
3Why is the signed 8-bit range −128 to 127 and not −127 to 127?
There are 256 patterns. Zero uses one pattern whose first bit is 0, leaving 127 positive patterns, while all 128 patterns starting with 1 are negative.
4A game stores the player's score in a 16-bit signed integer. A player reaches 32,767 and scores 10 more points. What does the game show?
wrap(32777, 16) = −32,759. The score wraps to a large negative number.
5Write a Python check that tells whether a + b would overflow a 32-bit signed int, without computing a result that is too big (pretend you are in Java).
MAX = 2_147_483_647 and MIN = -2_147_483_648. Overflow happens when b > 0 and a > MAX - b or b < 0 and a < MIN - b. Each test only computes values that stay in range.
Challenge
1Prove that, in n-bit two's complement, inverting all bits of x gives −x − 1. (Hint: what is x + (inverted x)?)
Each bit position of x and its inverse holds exactly one 1, so x + inv(x) is the all-ones pattern, which has value −1 in two's complement. So inv(x) = −1 − x, and therefore inv(x) + 1 = −x. This is why "invert and add 1" negates.
2Explain why -(-128) in an 8-bit signed integer is still −128.
+128 is not in the range. Invert 10000000 → 01111111, add 1 → 10000000, which is −128 again. In Java, Math.abs(Integer.MIN_VALUE) returns a negative number for the same reason.
3Python 3.11 and later refuse str(10 ** 5000) with a ValueError about a 4300-digit limit, even though the number itself is fine. Why might Python add such a limit, and how can a program that really needs it get around it?
Converting a huge integer to decimal text takes time that grows much faster than the number of digits, so a malicious input with millions of digits could freeze a server (a denial-of-service attack). The limit is a safety default. A program that really needs it can call sys.set_int_max_str_digits() with a larger limit, or work in hexadecimal, which is not limited.
Quiz
1. What is the range of an 8-bit signed (two's complement) integer?
2. What value does the 8-bit signed pattern 11111110 have?
3. In Java, int x = 2147483647; x = x + 1; What is x?
4. Why does Python print the exact value of 2 ** 100?
5. What is the safer way to find the middle index of a large array in Java?
6. What is 100 + 100 in an 8-bit signed integer?
Big idea: A1.4 asks students to understand the limitations of finite data representations, starting with integer bounds, and to keep them in mind when designing algorithms. This lesson also reuses the remainder operator from A1.1.
How to help: a car odometer or any digital counter is a great analogy: after 999 comes 000. Ask your teen to explain the Year 2038 problem to you in their own words.
Common difficulties:
- Forgetting that the leftmost bit has a negative weight.
- Negating by inverting only (forgetting to add 1).
- Believing "Python can't overflow, so this doesn't matter". Files, databases and other languages all have fixed widths.
- Off-by-one on ranges: the largest signed value is 2ⁿ⁻¹ − 1, not 2ⁿ⁻¹.