AP CSP Day 69: Binary Representation: Bits Required for a Range | Cycle 3
Share
The number of distinct values representable with n bits is 2^n. To represent values from 0 to k, you need 2^n ≥ k + 1. Off-by-one errors are common: the range 0 to 255 contains 256 values, not 255. AP questions may describe a scenario and ask for the minimum number of bits.
Study the Concept First (Optional) Click to expand ▼
Calculating Minimum Bits
The Formula
For m items, find the smallest n where 2^n ≥ m. Quick reference: 2^7 = 128, 2^8 = 256, 2^9 = 512, 2^10 = 1024. If m falls between two powers, round up.
Common Off-by-One Trap
The range 0 to 255 has 256 values (not 255). The range 1 to 100 has 100 values. Count carefully: integers from a to b inclusive is b − a + 1.
Practice Question
A sensor records temperature readings from −20 to 180 degrees, inclusive, in whole-degree increments. What is the minimum number of bits needed to represent all possible readings?
The range −20 to 180 inclusive contains 180 − (−20) + 1 = 201 distinct values. Since 2^7 = 128 (too small) and 2^8 = 256 (enough), the minimum is 8 bits.
B) 7 bits can only represent 128 values, not enough for 201. C) 9 bits (512 values) works but is not the minimum. D) 10 bits (1024 values) is far more than necessary.
Students forget to count both endpoints and the zero crossing. They calculate 180 − 20 = 160 instead of 180 − (−20) + 1 = 201.
First count how many distinct values you need. Then find the smallest power of 2 that is ≥ that count. The exponent is your answer.
Keep Practicing!
Consistent daily practice is the key to AP CSP success.
AP CSP Resources Get 1-on-1 Help