2.1 Overflow and round-offWhen fixed bits run out

In many programming languages, integers are stored using a fixed number of bits, for example 8, 16, 32 or 64. That limits the range of values: an 8-bit whole number can't go past 255, no matter what. When a calculation produces a value outside the range, the result is an overflow error. Depending on the language, the program might stop, or the extra bit might be lost so the value "wraps around" to a small number, like a car's trip odometer rolling from 999 back to 000.
?Wait, what was an overflow error in Unit 1?
Some languages hide this limit. They provide an abstraction in which the size of an integer is limited only by the computer's memory, so a number just grows as big as it needs to. The language on the AP Exam Reference Sheet is one of these: in exam pseudocode, integers don't overflow. So an exam question about overflow will always describe a fixed number of bits.
Round-off errors
Real numbers, the ones with decimal parts, have a different problem. Many of them can't be stored exactly. One third is 0.333... forever, and a computer has only a fixed number of bits for it, so it keeps an approximation. Even 0.1 has no exact binary form, the same way 1/3 has no exact decimal form. The tiny leftover is a round-off error.
| You ask for | Many languages store or show | Why |
|---|---|---|
| 1 / 3 | 0.3333333333333333 | The 3s never end; storage does |
| 0.1 + 0.2 | 0.30000000000000004 | 0.1 has no exact binary form |
| 0.1 + 0.2 = 0.3 | false | Two tiny round-off errors |
| 2 / 3 | 0.6666666666666666 | Cut off after about 16 digits |
?Wait, why can't 0.1 be exact in binary?
Round-off errors are usually tiny, but they matter in two places. First, comparisons: a program that checks whether 0.1 + 0.2 equals 0.3 may get false. Second, repetition: an error of one part in a quadrillion, repeated a billion times in a long simulation, can grow into something you notice. The course's takeaway: the fixed number of bits used to represent real numbers limits their range and precision, and that can cause round-off and other errors.
I thought about it. Show me
- (a) The true sum is 300. The largest 8-bit value is 255, so it overflows.
Why?
2⁸ = 256 patterns, 0 to 255. - Dropping the extra bit is the same as subtracting 256 (the value of the lost ninth bit): 300 - 256 = 44. The counter shows 44.
Why?
The lost bit is the 256s place. Wrap-around arithmetic like this is how many systems behave; the AP exam only expects you to recognize that an overflow happens. - (b) 128 + 127 = 255: fits. 200 + 56 = 256: overflows by 1. 15 + 240 = 255: fits.
Answer: (a) It stores 44 (300 overflows; 300 - 256 = 44). (b) 128 + 127 and 15 + 240 are safe; 200 + 56 overflows.
Stuck? Get a hint
- What is the biggest value 8 bits can hold?
- Compute each sum and compare it with 255.
- For the wrapped value, remove the 256s place: subtract 256.
- A6 + 9
- B15 - 15
- C7 × 2
- D12 + 4
Show the answer
D. 12 + 4 = 16, which is outside 0 to 15. The others give 15, 0 and 14, which all fit. 6 + 9 = 15 is the closest call, but 15 is the largest value 4 bits can hold, so it fits.
- AThe program has a syntax error.
- BReal numbers are stored with a fixed number of bits, so some can only be approximated, causing round-off error.
- CThe sum is too big for the computer, causing overflow.
- DDecimal numbers cannot be stored in binary at all.
Show the answer
B. Neither 0.1 nor 0.2 has an exact binary form, so each is stored as a close approximation, and the tiny errors show up in the sum. It's a round-off error, not overflow: the number is small, not too big.
- Fixed-size integers have a limited range. A result outside it is an overflow error.
- Some languages, including the exam's pseudocode, limit integers only by memory, so they don't overflow.
- Real numbers are stored with a fixed number of bits, so many are approximations: round-off errors.
- Overflow is about too big. Round-off is about not exact.