Representations of Integers • In the modern world, we use decimal, or base 10, notation to represent integers. • For example when we write 965, we mean 9∙102 + 6∙101 + 5∙100 . • We can represent numbers using any base b, where b is a positive integer greater than 1. • The bases b = 2 (binary), b = 8 (octal), and b= 16 (hexadecimal) are important for computing and communications • The ancient Mayans used base 20 and the ancient Babylonians used base 60. Base b Representations • We can use positive integer b greater than 1 as a base, because of this theorem: • Theorem 1 ○ Let b be a positive integer greater than 1. ○ Then if n is a positive integer, it can be expressed uniquely in the form: ○ n=a_k b^k+a_(k−1) b^(k−1)+…+a_1 b+a_0 ○ where k is a nonnegative integer, a_0,a_1,…,a_k are nonnegative integers less than b ○ and ak≠0. The a_j (j=0,…,k) are called the base-b digits of the representation. • The representation of n given in Theorem 1 is called the base b expansion of n • and is denoted by (a_k a_(k−1)…a_1 a_0 )_b. • We usually omit the subscript 10 for base 10 expansions. Binary Expansions • Most computers represent integers and do arithmetic with binary expansions of integers. • In these expansions, the only digits used are 0 and 1. • What is the decimal expansion of the integer that has (1 0101 1111)_2 as its binary expansion? ○ (1 0101 1111)_2 = 1∙2^8 + 0∙2^7 + 1∙2^6 + 0∙2^5 + 1⋅2^4 + 1∙2^3 + 1∙2^2 + 1∙2^1 + 1 = 351 • What is the decimal expansion of the integer that has (11011)2 as its binary expansion? ○ (11011)_2 = 1 ∙2^4 + 1∙2^3 + 0∙2^2 + 1∙2^1 + 1 = 27 Octal Expansions • The octal expansion (base 8) uses the digits {0,1,2,3,4,5,6,7}. • What is the decimal expansion of the number with octal expansion (7016)_8 ? ○ 7∙8^3 + 0∙8^2 + 1∙8^1 + 6 =3598 • What is the decimal expansion of the number with octal expansion (111)_8 ? ○ 1∙8^2 + 1∙8^1 + 1 = 64 + 8 + 1 = 73 Hexadecimal Expansions • The hexadecimal expansion needs 16 digits, but our decimal system provides only 10. • So letters are used for the additional symbols. • The hexadecimal system uses the digits {0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}. • The letters A through F represent the decimal numbers 10 through 15. • What is the decimal expansion of the number with hexadecimal expansion (2AE0B)_16 ? ○ 2∙〖16〗^4 + 10∙〖16〗^3 + 14∙〖16〗^2 + 0∙〖16〗^1 + 11 =175627 What is the decimal expansion of the number with hexadecimal expansion (E5)_16 ? ○ 14∙〖16〗^1 + 5 = 224 + 5 = 229 Base Conversion • To construct the base b expansion of an integer n: • Divide n by b to obtain a quotient and remainder. ○ 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. ○ q_0=bq_1+a_1, 0≤a_1 b • The remainder, a_1, is the second digit from the right in the base b expansion of n. • Continue by successively dividing the quotients by b • obtaining the additional base b digits as the remainder. • The process terminates when the quotient is 0. • Algorithm ○ q represents the quotient obtained by successive divisions by b, starting with q = n. ○ The digits in the base b expansion are the remainders of the division given by q mod b. ○ The algorithm terminates when q = 0 is reached. • Find the octal expansion of (12345)_10 ○ Successively dividing by 8 gives: ○ 12345 = 8 ∙ 1543 + 1 ○ 1543 = 8 ∙ 192 + 7 ○ 192 = 8 ∙ 24 + 0 ○ 24 = 8 ∙ 3 + 0 ○ 3 = 8 ∙ 0 + 3 ○ The remainders are the digits from right to left yielding (30071)_8. Comparison of Hexadecimal, Octal, and Binary Representations • Each octal digit corresponds to a block of 3 binary digits. • Each hexadecimal digit corresponds to a block of 4 binary digits. • So, conversion between binary, octal, and hexadecimal is easy. Conversion Between Binary, Octal, and Hexadecimal Expansions • Find the octal and hexadecimal expansions of (11 1110 1011 1100)_2. • To convert to octal, we group the digits into blocks of three • (011 111 010 111 100)_2, adding initial 0s as needed. • The blocks from left to right correspond to the digits 3,7,2,7, and 4. • Hence, the solution is (37274)_8. • To convert to hexadecimal, we group the digits into blocks of four • (0011 1110 1011 1100)_2, adding initial 0s as needed. • The blocks from left to right correspond to the digits 3,E,B, and C. • Hence, the solution is (3EBC)_16. Binary Addition of Integers • Algorithms for performing operations with integers using their binary expansions are important as computer chips work with binary numbers. Each digit is called a bit. • The number of additions of bits used by the algorithm to add two n-bit integers is O(n).
