Page 276 - Discrete Mathematics and Its Applications

4.2 Integer Representations and Algorithms 255

Exercises

1. Convert the decimal expansion of each of these integers essary, and translating each block of three binary digits
to a binary expansion. into a single octal digit.
a) 231 b) 4532 c) 97644 16. Show that the binary expansion of a positive integer can
2. Convert the decimal expansion of each of these integers be obtained from its octal expansion by translating each
to a binary expansion. octal digit into a block of three binary digits.
a) 321 b) 1023 c) 100632 17. Convert (7345321) 8 to its binary expansion and
3. Convert the binary expansion of each of these integers to (10 1011 1011) 2 to its octal expansion.
a decimal expansion. 18. Give a procedure for converting from the hexadecimal ex-
pansion of an integer to its octal expansion using binary
a) (1 1111) 2 b) (10 0000 0001) 2
notation as an intermediate step.
c) (1 0101 0101) 2 d) (110 1001 0001 0000) 2
4. Convert the binary expansion of each of these integers to 19. Give a procedure for converting from the octal expansion
a decimal expansion. of an integer to its hexadecimal expansion using binary
notation as an intermediate step.
a) (1 1011) 2 b) (10 1011 0101) 2
20. Explain how to convert from binary to base 64 expan-
c) (11 1011 1110) 2 d) (111 1100 0001 1111) 2
5. Convert the octal expansion of each of these integers to a sions and from base 64 expansions to binary expansions
binary expansion. and from octal to base 64 expansions and from base 64
expansions to octal expansions.
a) (572) 8 b) (1604) 8
21. Find the sum and the product of each of these pairs of
c) (423) 8 d) (2417) 8
numbers. Express your answers as a binary expansion.
6. Convert the binary expansion of each of these integers to
an octal expansion. a) (100 0111) 2 , (111 0111) 2
b) (1110 1111) 2 , (1011 1101) 2
a) (1111 0111) 2
b) (1010 1010 1010) 2 c) (10 1010 1010) 2 , (1 1111 0000) 2
c) (111 0111 0111 0111) 2 d) (10 0000 0001) 2 , (11 1111 1111) 2
22. Find the sum and product of each of these pairs of num-
d) (101 0101 0101 0101) 2
7. Convert the hexadecimal expansion of each of these in- bers. Express your answers as a base 3 expansion.
tegers to a binary expansion. a) (112) 3 ,(210) 3
a) (80E) 16 b) (135AB) 16 b) (2112) 3 ,(12021) 3
c) (ABBA) 16 d) (DEFACED) 16 c) (20001) 3 ,(1111) 3
8. Convert (BADFACED) 16 from its hexadecimal expan- d) (120021) 3 ,(2002) 3
sion to its binary expansion. 23. Find the sum and product of each of these pairs of num-
9. Convert (ABCDEF) 16 from its hexadecimal expansion to bers. Express your answers as an octal expansion.
its binary expansion. a) (763) 8 ,(147) 8
10. Convert each of the integers in Exercise 6 from a binary b) (6001) 8 ,(272) 8
expansion to a hexadecimal expansion. c) (1111) 8 ,(777) 8
11. Convert (1011 0111 1011) 2 from its binary expansion to d) (54321) 8 ,(3456) 8
its hexadecimal expansion. 24. Find the sum and product of each of these pairs of num-
12. Convert (1 1000 0110 0011) 2 from its binary expansion bers. Express your answers as a hexadecimal expan-
to its hexadecimal expansion. sion.
13. Show that the hexadecimal expansion of a positive integer a) (1AE) 16 , (BBC) 16
can be obtained from its binary expansion by grouping to- b) (20CBA) 16 , (A01) 16
gether blocks of four binary digits, adding initial zeros if c) (ABCDE) 16 , (1111) 16
necessary, and translating each block of four binary digits d) (E0000E) 16 , (BAAA) 16
into a single hexadecimal digit. 25. Use Algorithm 5 to find 7 644 mod 645.
14. Show that the binary expansion of a positive integer can 26. Use Algorithm 5 to find 11 644 mod 645.
be obtained from its hexadecimal expansion by translat- 2003
ing each hexadecimal digit into a block of four binary 27. Use Algorithm 5 to find 3 mod 99.
digits. 28. Use Algorithm 5 to find 123 1001 mod 101.
15. Show that the octal expansion of a positive integer can be 29. Show that every positive integer can be represented
obtained from its binary expansion by grouping together uniquely as the sum of distinct powers of 2. [Hint: Con-
blocks of three binary digits, adding initial zeros if nec- sider binary expansions of integers.]