Page 277 - Discrete Mathematics and Its Applications

256 4 / Number Theory and Cryptography

30. It can be shown that every integer can be uniquely repre- than one’s complement representations. To represent an inte-
sented in the form ger x with −2 n−1 ≤ x ≤ 2 n−1 − 1 for a specified positive
integer n, a total of n bits is used. The leftmost bit is used to
k
e k 3 + e k−1 3 k−1 + ··· + e 1 3 + e 0 ,
represent the sign. A 0 bit in this position is used for positive
integers, and a 1 bit in this position is used for negative inte-
where e j =−1, 0, or 1 for j = 0, 1, 2,...,k. Expan-
sions of this type are called balanced ternary expan- gers, just as in one’s complement expansions. For a positive
sions. Find the balanced ternary expansions of integer, the remaining bits are identical to the binary expan-
sion of the integer. For a negative integer, the remaining bits
a) 5. b) 13. c) 37. d) 79. n−1
are the bits of the binary expansion of 2 −|x|. Two’s com-
31. Show that a positive integer is divisible by 3 if and only plement expansions of integers are often used by computers
if the sum of its decimal digits is divisible by 3. because addition and subtraction of integers can be performed
easily using these expansions, where these integers can be ei-
32. Show that a positive integer is divisible by 11 if and only ther positive or negative.
if the difference of the sum of its decimal digits in even-
numbered positions and the sum of its decimal digits in 40. Answer Exercise 34, but this time find the two’s comple-
odd-numbered positions is divisible by 11. ment expansion using bit strings of length six.
41. Answer Exercise 35 if each expansion is a two’s comple-
33. Show that a positive integer is divisible by 3 if and only ment expansion of length five.
if the difference of the sum of its binary digits in even-
numbered positions and the sum of its binary digits in 42. Answer Exercise 36 for two’s complement expansions.
odd-numbered positions is divisible by 3. 43. Answer Exercise 37 for two’s complement expansions.
One’s complement representations of integers are used to 44. Answer Exercise 38 for two’s complement expansions.
simplify computer arithmetic. To represent positive and nega- 45. Show that the integer m with two’s complement
tive integers with absolute value less than 2 n−1 , a total of n bits representation (a n−1 a n−2 ...a 1 a 0 ) can be found us-
is used. The leftmost bit is used to represent the sign. A 0 bit ing the equation m =−a n−1 · 2 n−1 + a n−2 2 n−2 + ··· +
in this position is used for positive integers, and a 1 bit in this a 1 · 2 + a 0 .
position is used for negative integers. For positive integers,
the remaining bits are identical to the binary expansion of the 46. Give a simple algorithm for forming the two’s comple-
integer. For negative integers, the remaining bits are obtained ment representation of an integer from its one’s comple-
by first finding the binary expansion of the absolute value of ment representation.
the integer, and then taking the complement of each of these 47. Sometimes integers are encoded by using four-digit bi-
bits, where the complement ofa1isa0andthe complement nary expansions to represent each decimal digit. This pro-
ofa0isa1. duces the binary coded decimal form of the integer. For
instance, 791 is encoded in this way by 011110010001.
34. Find the one’s complement representations, using bit How many bits are required to represent a number with
strings of length six, of the following integers.
n decimal digits using this type of encoding?
a) 22 b) 31 c) −7 d) −19
A Cantor expansion is a sum of the form
35. What integer does each of the following one’s comple-
ment representations of length five represent? a n n!+ a n−1 (n − 1)! + ··· + a 2 2!+ a 1 1!,
a) 11001 b) 01101
c) 10001 d) 11111 where a i is an integer with 0 ≤ a i ≤ i for i = 1, 2,...,n.
36. If m is a positive integer less than 2 n−1 , how is the 48. Find the Cantor expansions of
one’s complement representation of −m obtained from a) 2. b) 7.
the one’s complement of m, when bit strings of length n c) 19. d) 87.
are used? e) 1000. f) 1,000,000.
37. How is the one’s complement representation of the sum ∗ 49. Describe an algorithm that finds the Cantor expansion of
of two integers obtained from the one’s complement rep- an integer.
resentations of these integers? ∗ 50. Describe an algorithm to add two integers from their Can-
tor expansions.
38. How is the one’s complement representation of the differ-
ence of two integers obtained from the one’s complement 51. Add (10111) 2 and (11010) 2 by working through each
representations of these integers? step of the algorithm for addition given in the text.
52. Multiply (1110) 2 and (1010) 2 by working through each
39. Show that the integer m with one’s complement
representation (a n−1 a n−2 ...a 1 a 0 ) can be found us- step of the algorithm for multiplication given in the text.
ing the equation m =−a n−1 (2 n−1 − 1) + a n−2 2 n−2 + 53. Describe an algorithm for finding the difference of two
···+ a 1 · 2 + a 0 . binary expansions.
Two’s complement representations of integers are also used 54. Estimate the number of bit operations used to subtract
to simplify computer arithmetic and are used more commonly two binary expansions.