Binary Numbers and Overflow
Aaliyah is playing a video game and her score hits 255. She grabs one more coin and the screen suddenly shows 0. Did the game erase her points? Computers store everything as 0s and 1s, and that has surprising consequences. By the end of this page you will know why her score reset.
Bits and bytes
A computer can only tell two states apart: on or off, which we write as 1 or 0. One of these is a bit (short for binary digit). A group of 8 bits is a byte.
With 1 bit you can make 2 patterns (0, 1). With 2 bits you get 4 patterns (00, 01, 10, 11). Every extra bit doubles the number of patterns, because each old pattern can end in a 0 or in a 1.
| Bits | Different values | Power of 2 |
|---|---|---|
| 1 | 2 | $2^1$ |
| 2 | 4 | $2^2$ |
| 3 | 8 | $2^3$ |
| 4 | 16 | $2^4$ |
| 8 | 256 | $2^8$ |
A bit is a single 0 or 1, and a byte is 8 bits. a) How many different values can be represented with 6 bits? b) How many bytes are needed to store exactly 40 bits?
A bit is a single 0 or 1, and a byte is 8 bits.
- a) How many different values can be represented with 6 bits?
- b) How many bytes are needed to store exactly 40 bits?
Converting between binary and decimal
You already use place values in decimal: in 352, the 3 means 3 hundreds. Binary works the same way, but each place is worth twice the place to its right, instead of ten times.
| Place value | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
|---|---|---|---|---|---|---|---|---|
| Bit | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 |
Binary to decimal
Add the place values wherever there is a 1.
Decimal to binary
Go from the largest place value down. If the place value fits in what is left, write a 1 and subtract it. Otherwise write a 0.
Convert the binary number $1011$ to decimal. Then convert the 8-bit binary number $00110101$ to decimal.
Convert the binary number $1011$ to decimal. Then convert the 8-bit binary number $00110101$ to decimal.
Convert the decimal number $25$ to an 8-bit binary number. Show the place values ($128, 64, 32, \ldots$) that you used.
Convert the decimal number $25$ to an 8-bit binary number. Show the place values ($128, 64, 32, \ldots$) that you used.
Counting what fits: choosing the number of bits
How many bits does a program need? Find the smallest $n$ such that $2^n$ is at least the number of things you must tell apart.
| Bits | $2^n$ |
|---|---|
| 9 | 512 |
| 10 | 1,024 |
| 16 | 65,536 |
| 32 | 4,294,967,296 |
A school with 300 clubs wants to give each club a unique ID number stored as a binary number with the same number of bits for every club. a) What is the minimum number…
A school with 300 clubs wants to give each club a unique ID number stored as a binary number with the same number of bits for every club.
- a) What is the minimum number of bits needed?
- b) If the school adds one more bit to the ID, how many total clubs can it identify?
- c) Explain in one or two sentences why adding one bit doubles the number of values.
Overflow
Back to Aaliyah's game. A counter has a fixed number of bits. With 8 bits the largest value is 255 (11111111). Add 1 and the true answer, 256, needs a ninth bit that the counter does not have.
In many systems the extra bit is lost and the counter "wraps around": it keeps only the remainder after dividing by $2^n$. For 8 bits, $256 \bmod 256 = 0$. So Aaliyah's 255 plus 1 shows 0.
A simple calculator stores unsigned whole numbers using only 4 bits, so the largest value it can hold is $15$. Aaliyah asks it to compute $9 + 8$. a) What is the true…
A simple calculator stores unsigned whole numbers using only 4 bits, so the largest value it can hold is $15$. Aaliyah asks it to compute $9 + 8$.
- a) What is the true sum, written in decimal and in binary?
- b) What happens inside the calculator, and what value does it end up storing? (Hint: think of what happens to the extra bit.)
- c) What is the name of this kind of error?
Marcus is writing a coin-collecting game. The score is stored in an 8-bit unsigned counter, and each coin is worth 25 points. The game allows up to 10,000 coins in a…
Marcus is writing a coin-collecting game. The score is stored in an 8-bit unsigned counter, and each coin is worth 25 points. The game allows up to 10,000 coins in a level.
- a) After how many coins does the counter first overflow? What score does the screen show after 11 coins? Assume that overflow wraps around to the remainder when divided by $256$.
- b) Explain why a player would see this as a bug.
- c) What is the minimum number of bits Marcus needs so that the score never overflows, even if a player collects all 10,000 coins? Show the numbers that support your answer.
Round-off errors
Overflow is about numbers that are too big. A different problem comes with decimals. A computer has only a limited number of bits for each number, so many decimals cannot be stored exactly. The fraction $\tfrac{1}{3}$ is $0.333\ldots$ in decimal, which never ends. In binary, even $0.1$ never ends, so the computer keeps a close approximation.
Tiny errors add up. In many languages, 0.1 + 0.2 gives something like 0.30000000000000004, so 0.1 + 0.2 = 0.3 is false.
In many programming languages, the expression 0.1 + 0.2 = 0.3 evaluates to false, even though it is true in math class. a) Explain why this happens. Use the idea that…
In many programming languages, the expression 0.1 + 0.2 = 0.3 evaluates to false, even though it is true in math class.
- a) Explain why this happens. Use the idea that computers store numbers using a limited number of bits.
- b) What is the name for this kind of error?
- c) Describe a safer way for a program to check whether two decimal results are "equal."
One pattern, many meanings
The 8 bits 01000001 are the number 65. They are also the letter "A" in the ASCII character code, and they could be the brightness of one pixel. The pattern itself carries no label. The program, the file type, or the context tells the computer how to interpret the bits. That is an example of abstraction.
-
Text: each character gets a number (ASCII, Unicode).
-
Colors: a pixel is often three numbers (red, green, blue), each 0 to 255, so 3 bytes per pixel.
-
Sound: analog sound is a smooth wave. A computer samples it, measuring the height of the wave many times per second and storing each measurement as a number.
More samples per second and more bits per sample give a closer copy of the original. Fewer samples or fewer bits lose detail.
The 8-bit pattern $01000001$ could mean the number $65$, the letter "A", or the brightness of one pixel in a photo. a) Explain how a computer "knows" which meaning to…
The 8-bit pattern $01000001$ could mean the number $65$, the letter "A", or the brightness of one pixel in a photo.
- a) Explain how a computer "knows" which meaning to use for the same pattern.
- b) A microphone signal is sampled 1,000 times per second for 3 seconds. Each sample is stored with 8 bits. How many bytes are needed for the recording?
- c) Compare using 2 bits per sample with using 8 bits per sample. How many different levels does each allow, and how does this affect how closely the digital recording matches the original analog sound?
Back to the start: Aaliyah's 8-bit score could not store 256, so it wrapped around to 0. That is overflow.