AP® Computer Science Principles · Big Idea 2 · Topic 2.1
Limits of Bits: Overflow and Round-off
A computer stores numbers in a fixed number of bits, so integers hit a hard maximum called overflow, and most fractions can only be rounded to the nearest storable value, never stored exactly.
A bit pattern of fixed width can only hold so many distinct values. With b bits, an unsigned counter can represent exactly 2b different values: 0 through 2b minus 1. Try to go one higher and there is no pattern left to hold it, so the counter wraps back around to 0. That wraparound is overflow, and it is not a bug in any one program, it is a direct consequence of the hardware giving every number a fixed number of slots.
Fractions run into a different wall. Binary place values after the point are halves, quarters, eighths, sixteenths, each one a power of two. One half, 0.5, lands exactly on one of those slots. One third does not. No finite string of halves, quarters, and eighths ever adds up to exactly one third, so the computer stores the closest value it can reach and quietly drops the rest. This is round-off: not a mistake, but the honest limit of a finite number of bits trying to describe an infinite decimal.
These two limits, overflow for integers and round-off for fractions, are the reason Big Idea 2 keeps returning to the idea that bits are a finite resource. Every encoding choice later in the unit, colors, sound, images, inherits this same ceiling and the same fuzziness, so understanding overflow and round-off here is what makes the rest of the data unit make sense.
Key terms
- overflow
- When a calculation produces a value too large for the fixed number of bits available, causing it to wrap around.
- round-off
- The small error introduced when a real number that cannot be stored exactly is approximated by the nearest representable value.
- unsigned integer
- A whole number representation that stores only non-negative values, using all its bits for magnitude.
- bit width
- The fixed number of bits allotted to store a single value, which sets the range of values it can represent.
Watch it explained
- How it worksHow does a fixed bit width put a hard ceiling and floor on the integers a program can hold?
- How it worksWalk me through why certain real numbers only ever get stored as approximations.
- Worked exampleFind the largest positive integer a 16 bit unsigned counter is able to represent.
- Worked exampleFind the stored approximation when a program tries to represent one third using only 4 bits after the binary point.
- Common mistakeWhy isn't 0.1 added to 0.2 exactly equal to 0.3 inside a computer?
Check yourself
End of topic.