AP Computer Science Principles · Unit 2 lecture · Part 3 of 11 · 7 min

2.1 Binary numbers: how many valuesEach bit doubles your options

Mr. Thompkins
Here's a question the exam asks in a dozen disguises: how many bits do you need? It looks like it needs a calculator. It doesn't. It needs one pattern.

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.

Patterns with n bits21 bit42 bits83 bits164 bits325 bits646 bits1287 bits2568 bits
Each extra bit doubles the number of patterns. 8 bits, one byte, make 256.

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.

BitsPatterns (2ⁿ)Whole numbers 0 to 2ⁿ - 1Enough for
380 to 7Days of the week
5320 to 31Letters A to Z
8 (1 byte)2560 to 255One color channel
95120 to 511300 student IDs
1665,5360 to 65,535Every seat in a big stadium
2416,777,2160 to 16,777,215Every screen color
How many patterns n bits make, and what that is enough for.
?Wait, why is 2⁸ equal to 256?
Double 1 eight times: 2, 4, 8, 16, 32, 64, 128, 256. Each doubling is one more bit. It helps to know the powers of 2 up to 2¹⁰ = 1,024 by heart.

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?
Both, really. With n bits there are 2ⁿ patterns, so you can represent 2ⁿ different values. If those values are whole numbers from 0, the biggest one is 2ⁿ - 1. More bits, more values, and a higher maximum.
Pause and think
A system uses 10 bits per ID. A manager wants to double the number of possible IDs. How many bits does it need now?
I thought about it. Show me
11. Adding one bit doubles the number of patterns, from 2¹⁰ = 1,024 to 2¹¹ = 2,048. You don't double the bits; doubling the bits to 20 would multiply the number of IDs by 1,024.
Minimum bits
A school has 300 students and wants to give each a unique ID using the same number of bits for everyone. (a) What is the minimum number of bits? (b) How many students could the school add before it needs another bit?
  1. List powers of 2 near 300: 2⁸ = 256 and 2⁹ = 512.
  2. 256 patterns aren't enough for 300 students. 512 are. So the minimum is 9 bits.
    Why?
    Find the smallest n with 2ⁿ ≥ 300.
  3. (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
  1. What is 2⁸? What is 2⁹?
  2. Which is the first one that is at least 300?
  3. Then subtract 300 from that number of patterns.
Check yourself
A game stores each player's level using 5 bits, starting at level 0. What is the highest level it can store?
  1. A5
  2. B31
  3. C32
  4. 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.

Check yourself
How many more values can be represented with 9 bits than with 8 bits?
  1. A1
  2. B2 times as many
  3. C9 more
  4. 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.

Exam tip from Mr. T

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.