Number Systems and
• Learn the binary, octal, decimal, and hexadecimal number systems.
• Be able to abbreviate binary numbers as octal or hexadecimal numbers.
• Be able to convert an int to its binary representation and back.
• Understand the basics of base-2 logarithms.
In Sec 1.1, we introduced briefly binary, octal, decimal, and hexadecimal sys-
tems. The binary number system was said to be important because computers
store integers using binary. But binary numbers —and base-2 logarithms, which
we explain in this Appendix— arise in more ways than simply the storage of inte-
gers. For example, they arise in the explanation of the running time of many algo-
rithms, such as exponentiation x y , binary search, and quick sort.
We explain these number systems in more detail, showing how one can con-
vert an integer from one number system to another. With regard to logarithms, we
explain them only enough so that the running times of various algorithms can be
understood, and we keep the explanation simple.
Below, we show the “digits” that are used in counting in four number systems:
binary : 0 1
octal : 0 1 2 3 4 5 6 7
decimal : 0 1 2 3 4 5 6 7 8 9
hexadecimal : 0 1 2 3 4 5 6 7 8 9 A B C D E F
The number of digits used is called the base of the number system. The binary
system has base 2; the octal system, base 8; the decimal system, base 10; and the