Page 268 - Discrete Mathematics and Its Applications

4.2 Integer Representations and Algorithms 247

EXAMPLE 2 What is the decimal expansion of the number with octal expansion (7016) 8 ?

Solution: Using the definition of a base b expansion with b = 8 tells us that
2
3
(7016) 8 = 7 · 8 + 0 · 8 + 1 · 8 + 6 = 3598. ▲
Sixteen different digits are required for hexadecimal expansions. Usually, the hexadecimal
digits used are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, and F, where the letters A through F
represent the digits corresponding to the numbers 10 through 15 (in decimal notation).

EXAMPLE 3 What is the decimal expansion of the number with hexadecimal expansion (2AE0B) ?
16
Solution: Using the definition of a base b expansion with b = 16 tells us that

4
3
2
(2AE0B) 16 = 2 · 16 + 10 · 16 + 14 · 16 + 0 · 16 + 11 = 175627. ▲
Each hexadecimal digit can be represented using four bits. For instance, we see that
(1110 0101) 2 = (E5) 16 because (1110) 2 = (E) 16 and (0101) 2 = (5) 16 . Bytes, which are bit
strings of length eight, can be represented by two hexadecimal digits.

BASE CONVERSION We will now describe an algorithm for constructing the base b expan-
sion of an integer n. First, divide n by b to obtain a quotient and remainder, that is,

n = bq 0 + a 0 , 0 ≤ a 0 <b.

The remainder, a 0 , is the rightmost digit in the base b expansion of n. Next, divide q 0 by b to
obtain

q 0 = bq 1 + a 1 , 0 ≤ a 1 <b.

We see that a 1 is the second digit from the right in the base b expansion of n. Continue this
process, successively dividing the quotients by b, obtaining additional base b digits as the
remainders. This process terminates when we obtain a quotient equal to zero. It produces the
base b digits of n from the right to the left.

EXAMPLE 4 Find the octal expansion of (12345) 10 .

Solution: First, divide 12345 by 8 to obtain

12345 = 8 · 1543 + 1.

Successively dividing quotients by 8 gives

1543 = 8 · 192 + 7,
192 = 8 · 24 + 0,
24 = 8 · 3 + 0,
3 = 8 · 0 + 3.

The successive remainders that we have found, 1, 7, 0, 0, and 3, are the digits from the right to
the left of 12345 in base 8. Hence,

(12345) 10 = (30071) 8 . ▲