I am reading Computer Science: An Overview Eleventh Edition By J. Glenn Brookshear

I believe this book was once assigned as optional reading material for CS50x

A typical dictionary in a word processor contains approximately 25,000 entries, which means an individual entry can be identified by an integer in the range of 0 to 24,499. This means that a particular entry in the dictionary can be identified by a pattern of only 15 bits.

How does the logic/math work on this?


if you assign a unique number to each dictionary entry and the numbers are assigned sequentially, they run from 0 to 24,999, as you said. Now, it's just a matter of converting 24,999 to binary.

If you wanted to represent 11 different entries, you would need a binary number that can represent decimal 11. Decimal 11 = binary 1011. That's 4 bits. Similarly, 24,999 is represented by a 15 digit binary number, 110 0001 1010 0111.

An easier way is to find the smallest power of 2 that is larger than the target number. In my example of 11, the smallest power of 2 greater than 11 is 16, or 2 to the 4th power (2^4) For 25,000 you would need to go to 32768 or 2^15.

If this answers your question to your satisfaction, please mark this question as answered. Let's keep up on forum housekeeping. ;-)


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .