Show that the integer m with one's complement

Problem 1E Convert the decimal expansion of each of these integers to a binary expansion. a) 231 b) 4532 c) 97644

Problem 59E Show that Algorithm 4 uses O(q log a) bit operations, assuming that a > d.

Problem 2E Convert the decimal expansion of each of these integers to a binary expansion. a) 321 b) 1023 c) 100632

Problem 5E Convert the octal expansion of each of these integers to a binary expansion. a) (572)8 ________________ b) (1604)8 ________________ c) (423)8 ________________ d) (2417)8

Problem 3E Convert the binary expansion of each of these integers to a decimal expansion. a) (1 1111)2 ________________ b) (10 0000 0001)2 ________________ c) (1 0101 0101)2 ________________ d) (110 1001 0001 0000)2

Problem 6E Convert the binary expansion of each of these integers to an octal expansion. a) (1111 0111)2 ________________ b) (1010 1010 1010)2 ________________ c) (111 0111 0111 0111)2 ________________ d) (101 0101 0101 0101)2

Problem 7E Convert the hexadecimal expansion of each of these integers to a binary expansion. a) (80E)16 ________________ b) (135AB)16 ________________ c) (ABBA)16 ________________ d) (DEFACED)16

Problem 8E Convert (BADFACED)16 from its hexadecimal expansion to its binary expansion.

Problem 9E Convert (ABCDEF)16 from its hexadecimal expansion to its binary expansion.

Problem 10E Convert each of the integers in Exercise 6 from a binary expansion to a hexadecimal expansion. 1. (1111 0111)2 2. (1010 1010 1010)2 3. (111 0111 0111 0111)2 4. (101 0101 0101 0101)2

Problem 11E Convert (1011 0111 1011)2 from its binary expansion to its hexadecimal expansion.

Problem 12E Convert (1 1000 0110 0011)2 from its binary expansion to its hexadecimal expansion.

Problem 13E Show that the hexadecimal expansion of a positive integer can be obtained from its binary expansion by grouping together blocks of four binary digits, adding initial zeros if necessary, and translating each block of four binary digits into a single hexadecimal digit.

Problem 14E Show that the binary expansion of a positive integer can be obtained from its hexadecimal expansion by translating each hexadecimal digit into a block of four binary digits.

Problem 15E Show that the octal expansion of a positive integer can be obtained from its binary expansion by grouping together blocks of three binary digits, adding initial zeros if necessary, and translating each block of three binary digits into a single octal digit.

Problem 16E Show that the binary expansion of a positive integer can be obtained from its octal expansion by translating each octal digit into a block of three binary digits.

Problem 17E Convert (7345321)8 to its binary expansion and (10 1011 1011)2 to its octal expansion.

Problem 18E Give a procedure for converting from the hexadecimal expansion of an integer to its octal expansion using binary notation as an intermediate step.

Problem 19E Give a procedure for converting from the octal expansion of an integer to its hexadecimal expansion using binary notation as an intermediate step.

Problem 21E Find the sum and the product of each of these pairs of numbers. Express your answers as a binary expansion. a) (100 0111)2,(111 0111)2 ________________ b) (1110 1111)2, (1011 1101)2 ________________ c) (10 1010 1010)2,(1 1111 0000)2 ________________ d) (10 0000 0001)2,(11 1111 1111)2

Problem 21E Find the sum and the product of each of these pairs of numbers. Express your answers as a binary expansion. a) ?(100 0111)2,(111 0111)2 b) ?(1110 1111)2, (1011 1101)2 c) ?(10 1010 1010)2,(1 1111 0000)2 d) ?(10 0000 0001)2,(11 1111 1111)2

Problem 22E Find the sum and product of each of these pairs of numbers. Express your answers as a base 3 expansion. a) (112)3, (210)3 ________________ b) (2112)3, (12021)3 ________________ c) (20001)3, (1111)3 ________________ d) (120021)3, (2002)3

Problem 23E Find the sum and product of each of these pairs of numbers. Express your answers as an octal expansion. a) (763)8, (l47)8 ________________ b) (6001)8, (272)8 ________________ c) (1111)8, (777)8 ________________ d) (54321)8, (3456)8

Problem 24E Find the sum and product of each of these pairs of numbers. Express your answers as a hexadecimal expansion. a) (1AE)16, (BBC)16 ________________ b) (20CBA)16,(A01)16 ________________ c) (ABCDE)16, (1111)16 ________________ d) (E0000E)16, (BAAA)16

Problem 25E Use Algorithm 5 to find 7644 ?mod? 645.

Problem 26E Use Algorithm 5 to find 11644 mod 645.

Problem 27E Use Algorithm 5 to find 32003 mod 99.

Problem 28E Use Algorithm 5 to find 1231001 mod 101.

Problem 29E Show that every positive integer can be represented uniquely as the sum of distinct powers of 2. [Hint: Consider binary expansions of integers.]

Problem 30E It can be shown that every integer can be uniquely represented in the form ek3k + ek-13k-1+···+ e13 +e0, where ej = -1, 0, or 1 for j = 0, 1. 2,···,k. Expansions of this type are called balanced ternary expansions. Find the balanced ternary expansions of a) 5. b) 13. c) 37. d) 79.

Problem 31E Show that a positive integer is divisible by 3 if and only if the sum of its decimal digits is divisible by 3.

Problem 32E Show that a positive integer is divisible by 11 if and only if the difference of the sum of its decimal digits in even-numbered positions and the sum of its decimal digits in odd-numbered positions is divisible by 11.

Problem 34E Find the one's complement representations, using bit strings of length six, of the following integers. a) 22 b) 31 c) -7 d) -19

Problem 33E Show that a positive integer is divisible by 3 if and only if the difference of the sum of its binary digits in even-numbered positions and the sum of its binary digits in odd-numbered positions is divisible by 3. One's complement representations of integers are used to simplify computer arithmetic. To represent positive and negative integers with absolute value less than 2n-1, a total of n bits is used. The leftmost bit is used to 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 integers. For positive integers, the remaining bits are identical to the binary expansion of the integer. For negative integers, the remaining bits are obtained by first finding the binary expansion of the absolute value of the integer, and then taking the complement of each of these bits, where the complement of a 1 is a 0 and the complement of a 0 is a 1.

Problem 35E What integer docs each of the following one's complement representations of length five represent? a) 11001 ________________ b) 01101 ________________ c) 10001 ________________ d) 11111

Problem 36E If m is a positive integer less than 2n-l, how is the one's complement representation of -m obtained from the one's complement of m, when bit strings of length n are used?

Problem 37E How is the one's complement representation of the sum of two integers obtained from the one's complement representations of these integers?

Problem 38E How is the one's complement representation of the difference of two integers obtained from the one's complement representations of these integers?

Problem 39E Show that the integer m with one's complement representation (an-1an-2…a1a2) can be found using the equation m =- an-1(2n-1 - 1) + an-22n-2+··· +a1.2+a0. Two's complement representations of integers are also used to simplify computer arithmetic and are used more commonly than one's complement representations. To represent an integer x with -2n-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 represent the sign. A 0 bit in this position is used for positive integers, and a I bit in this position is used for negative integers. just as in one's complement expansions. For a positive integer, the remaining bits are identical to the binary expan-sion of the integer. For a negative integer, the remaining bits are the bits of the binary expansion of 2 n-1 - |x|. Two's complement expansions of integers are often used by computers because addition and subtraction of integers can be performed easily using these expansions, where these integers can be either positive or negative.

Problem 40E Two's complement representations of integers are also used to simplify computer arithmetic and are used more commonly than one's complement representations. To represent an integer x with -2n-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 represent the sign. A 0 bit in this position is used for positive integers, and a I bit in this position is used for negative integers. just as in one's complement expansions. For a positive integer, the remaining bits are identical to the binary expansion of the integer. For a negative integer, the remaining bits are the bits of the binary expansion of 2 n-1 - |x|. Two's complement expansions of integers are often used by computers because addition and subtraction of integers can be performed easily using these expansions, where these integers can be either positive or negative. Answer Exercise 34, but this time find the two's complement expansion using bit strings of length six. EXERCISE 35 One's complement representations of integers are used to simplify computer arithmetic. To represent positive and negative integers with absolute value less than 2n-1, a total of n bits is used. The leftmost bit is used to 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 integers. For positive integers, the remaining bits are identical to the binary expansion of the integer. For negative integers, the remaining bits are obtained by first finding the binary expansion of the absolute value of the integer, and then taking the complement of each of these bits, where the complement of a 1 is a 0 and the complement of a 0 is a 1. Find the one's complement representations, using bit strings of length six, of the following integers. a) 22 b) 31 c) -7 d) -19

Problem 41E Two's complement representations of integers are also used to simplify computer arithmetic and are used more commonly than one's complement representations. To represent an integer x with -2n-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 represent the sign. A 0 bit in this position is used for positive integers, and a I bit in this position is used for negative integers. just as in one's complement expansions. For a positive integer, the remaining bits are identical to the binary expansion of the integer. For a negative integer, the remaining bits are the bits of the binary expansion of 2 n-1 - |x|. Two's complement expansions of integers are often used by computers because addition and subtraction of integers can be performed easily using these expansions, where these integers can be either positive or negative. Answer Exercise 35 if each expansion is a two's complement expansion of length five. EXERCISE 35 One's complement representations of integers are used to simplify computer arithmetic. To represent positive and negative integers with absolute value less than 2n-1, a total of n bits is used. The leftmost bit is used to 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 integers. For positive integers, the remaining bits are identical to the binary expansion of the integer. For negative integers, the remaining bits are obtained by first finding the binary expansion of the absolute value of the integer, and then taking the complement of each of these bits, where the complement of a 1 is a 0 and the complement of a 0 is a 1. What integer docs each of the following one's complement representations of length five represent? a) 11001 b) 01101 c) 10001 d) 11111

Problem 42E Two’s complement representations of integers are also used to simplify computer arithmetic and are used more commonly thank one’s complement representation. To represent an integer x with for a specified positive integer n, a total of n bits is used. The leftmost bit is used to 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 integers. just as in one's complement expansions. For a positive integer, the remaining bits are identical to the binary expansion of the integer. For a negative integer, the remaining bits are the bits of the binary expansion of . Two's complement expansions of integers are often used by computers because addition and subtraction of integers can be performed easily using these expansions, where these integers can be either positive or negative. Answer Exercise 36 for two's complement expansions. EXERCISE 36: One's complement representations of integers are used to simplify computer arithmetic. To represent positive and negative integers with absolute value less than 2n-1, a total of n bits is used. The leftmost bit is used to 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 integers. For positive integers, the remaining bits are identical to the binary expansion of the integer. For negative integers, the remaining bits are obtained by first finding the binary expansion of the absolute value of the integer, and then taking the complement of each of these bits, where the complement of a 1 is a 0 and the complement of a 0 is a 1. If m is a positive integer less than 2n-1, how is the one's complement representation of -m obtained from the one's complement of m, when bit strings of length n are used?

Problem 43E Answer Exercise 37 for two's complement expansions.

Problem 44E Answer Exercise 38 for two's complement expansions.

Problem 45E Show that the integer m with two's complement representation (an-1an-2···a1a0) can be found using the equation m =- an-1·2n-1 + an-22n-2+··· +a1.2+a0.

Problem 46E Give a simple algorithm for forming the two's complement representation of an integer from its one's complement representation.

Problem 47E Sometimes integers are encoded by using four-digit binary expansions to represent each decimal digit. This produces the binary coded decimal form of the integer. For instance. 791 is encoded in this way by 011110010001. How many bits are required to represent a number with n decimal digits using this type of encoding? A Cantor expansion is a sum of the form ann! + an-1(n - 1)! + a22! + a11!. where a1is an integer with 0 ? ai ? i for i= 1,2,···n.

Problem 48E Find the Cantor expansions of a) 2. ________________ b) 7. ________________ c) 19. ________________ d) 87. ________________ e) 1000. ________________ f) 1,000,000.

Problem 52E Multiply (1110)2 and (1010)2 by working through each step of the algorithm for multiplication given in the text.

Problem 51E Add (10111)2 and (11010)2 by working through each step of the algorithm for addition given in the text.

Problem 49E Describe an algorithm that finds the Cantor expansion of an integer.

Problem 53E Describe an algorithm for finding the difference of two binary expansions.

Problem 50E Describe an algorithm to add two integers from their Cantor expansions.

Problem 54E Estimate the number of bit operations used to subtract two binary expansions.

Problem 55E Devise an algorithm that, given the binary expansions of the integers a and b. determines whether a > b, a = b, or a

Problem 56E How many bit operations does the comparison algorithm from Exercise 55 use when the larger of a and b has n bits in its binary expansion?

Problem 57E Estimate the complexity of Algorithm 1 for finding the base b expansion of an integer n in terms of the number of divisions used.

Problem 58E Show that Algorithm 5 uses O((log m)2 log n) bit operations to find bn mod m.

Problem 4E Convert the binary expansion of each of these integers to a decimal expansion. a) (1 1011)2 ________________ b) (10 1011 0101)2 ________________ c) (11 1011 1110)2 ________________ d) (1111 1100 0001 1111)2