2.1 Binary numbers: how many valuesEach bit doubles your options

One bit has 2 patterns: 0 and 1. Two bits have 4: 00, 01, 10, 11. Three bits have 8. Every time you add a bit, each old pattern can be followed by a 0 or a 1, so the number of patterns doubles. With n bits there are 2ⁿ different patterns.
If you use those patterns for whole numbers starting at 0, the largest is 2ⁿ - 1, because 0 uses up one pattern. Eight bits hold 0 to 255, not 0 to 256. Four bits hold 0 to 15. That "minus 1" is one of the most common slips on the exam.
| Bits | Patterns (2ⁿ) | Whole numbers 0 to 2ⁿ - 1 | Enough for |
|---|---|---|---|
| 3 | 8 | 0 to 7 | Days of the week |
| 5 | 32 | 0 to 31 | Letters A to Z |
| 8 (1 byte) | 256 | 0 to 255 | One color channel |
| 9 | 512 | 0 to 511 | 300 student IDs |
| 16 | 65,536 | 0 to 65,535 | Every seat in a big stadium |
| 24 | 16,777,216 | 0 to 16,777,215 | Every screen color |
?Wait, why is 2⁸ equal to 256?
To find the minimum number of bits for some number of items, find the smallest n with 2ⁿ at least that number. For 100 club IDs: 2⁶ = 64 is too few, 2⁷ = 128 is enough, so 7 bits. You don't need logarithms, just the list of powers.
?Wait, does a bigger number of bits mean bigger numbers or more numbers?
I thought about it. Show me
- List powers of 2 near 300: 2⁸ = 256 and 2⁹ = 512.
- 256 patterns aren't enough for 300 students. 512 are. So the minimum is 9 bits.
Why?
Find the smallest n with 2ⁿ ≥ 300. - (b) 9 bits give 512 IDs. 512 - 300 = 212 more students fit before a tenth bit is needed.
Answer: (a) 9 bits. (b) 212 more students (512 IDs in all).
Stuck? Get a hint
- What is 2⁸? What is 2⁹?
- Which is the first one that is at least 300?
- Then subtract 300 from that number of patterns.
- A5
- B31
- C32
- D64
Show the answer
B. 5 bits give 2⁵ = 32 patterns. Starting at 0, they cover 0 to 31, so 31 is the highest. 32 is the trap: it's the number of patterns, not the largest value.
- A1
- B2 times as many
- C9 more
- D8 times as many
Show the answer
B. Adding one bit doubles the number of patterns: 256 with 8 bits, 512 with 9. That's twice as many, which is 256 more, not 1 or 9 more.
Memorize the powers of 2 from 2¹ = 2 to 2¹⁰ = 1,024. "Minimum bits" questions become a quick look-up, and you save time for the code questions.
- n bits make 2ⁿ patterns. Each extra bit doubles the count.
- As whole numbers from 0, n bits hold 0 to 2ⁿ - 1.
- Minimum bits for k items: the smallest n with 2ⁿ ≥ k.
- 8 bits (a byte): 256 values. 24-bit color: 16,777,216 colors.