CSE 1400 Applied Discrete Mathematics Conversions Between ...

CSE 1400 Applied Discrete Mathematics Conversions Between Number Systems

Department of Computer Sciences College of Engineering Florida Tech Fall 2011

Conversion Algorithms: Decimal to Another Base 1

Conversion of Natural Numbers 1 Conversion of Integers 3 Biased Notation for Integers 4 Conversion of Rational Numbers 5 Conversion of Floating Point Numbers 7

Problems on Converting Decimal to Another Base 7 Conversion Algorithms: Another Base to Decimal 8

Conversion of Natural Numbers 9 Conversion of Integers 10 Conversion of Rational Numbers 11 Conversion of Floating Point Numbers 11 Floating Point Arithmetic 12 Machine Epsilon 13

Problems on Converting Another Base to Decimal 14

Abstract Decimal notation using Arabic numerals is the standard system for writing numbers in everyday life. However, in many computing applications, other notations are used. Chiefly: binary and hexadecimal. Learning algorithms to translate names between these numerical systems forms a foundation for developing translations between more complex languages.

Conversion Algorithms: Decimal to Another Base

Conversion of Natural Numbers The unsigned whole numbers, the natural numbers, written in decimal 0, 1, 2, 3, 4, 5, . . . can be converted to binary by repeated division

cse 1400 applied discrete mathematics conversions between number systems 2

by 2. Dividing a number by 2 produces one of two remainders: r = 0 or r = 1. The natural numbers can be converted to hexadecimal by repeated division by 16. Dividing a number by 16 produces one of 16 remainder: r = 0 through r = 15 = F. ? Convert q = 14 to binary.

Repeatedly divide 14 and following quotients by 2 pushing the remainder bits onto a stack.

Repeated Remaindering Mod 2 Quotients 14 7 3 1 Remainders 0 1 1 1

(14)10 = (1110)2 ? Convert q = 14 to hexadecimal.

Repeatedly divide 14 and following quotients by 16 pushing the remainder hex-digits onto a stack.

Repeated Remaindering Mod 16 Quotients 14 Remainders E

(14)10 = (E)16 ? Convert q = 144 to binary.

Repeated Remaindering Mod 2 Quotients 144 72 36 18 9 4 2 1 Remainders 0 0 0 0 1 0 0 1

(144)10 = (1001 0000)2 ? Convert q = 144 to hexadecimal.

Repeated Remaindering Mod 16 Quotients 144 9 Remainders 0 9

(144)10 = (90)16

? Convert q = 143 to binary.

cse 1400 applied discrete mathematics conversions between number systems 3

Repeated Remaindering Mod 2 Quotients 143 71 35 17 8 4 2 1 Remainders 1 1 1 1 0 0 0 1

(143)10 = (1000 1111)2 ? Convert q = 143 to hexadecimal.

Repeated Remaindering Mod 16 Quotients 143 8 Remainders F 8

(143)10 = (8F)16 ? Convert q = 255 to binary.

Repeated Remaindering Mod 2 Quotients 255 127 63 31 15 7 3 1 Remainders 1 1 1 1 1 1 1 1

(255)10 = (1111 1111)2 ? Convert 161 to binary.

Repeated Remaindering Mod 2 Quotients 161 80 40 20 10 5 2 1 Remainders 1 0 0 0 0 1 0 1

(161)10 = (1010 0001)2 ? Convert 161 to ternary.

Repeated Remaindering Mod 3 Quotients 161 53 17 5 1 Remainders 2 2 2 2 1

(161)10 = (12222)3. Notice that 161 = 1 ? 34 + 2 ? 33 + 2 ? 32 + 2 ? 31 + 2 ? 30

cse 1400 applied discrete mathematics conversions between number systems 4

Conversion of Integers

The signed integers can be represented in two's complement notation. To write a decimal integer m in two's complement notation do the following.

1. Convert the natural number |m| to binary using repeated remaindering as described in the previous section.

2. Append a leading sign bit 0.

3. If m 0, return the result of step 2. Otherwise, if m < 0, return the two's complement of the result of step 2.

The two's complement operation is performed as follows.

1. From right-to-left, copy each bit up to and including the first 1.

2. Flip (one's complement) the remaining bits to the left.

The idea is: A number m and its negative -m add to 0. Therefore, if m = 0100 1100 is a signed integer written in two's complement notation, then m and m's complement (its negative) m add to 0.

1. This integer m = 0100 1100 is positive: It's leading, left-most, bit is 0.

2. The value of m is decimal 76.

3. The two's complement of m is m = 1011 0100.

The sum of m and m is shown below with carry bits on the top

row. c 1 11111000 m=01001100 m=10110100

00000000

By construction, the sum of m and it's two's complement m is 2s where s is the word length, size, or number of bits in m.

m

+

m

=

2s

=

1

s

0000 ?

0's

? ? 0000

To write 2s in binary requires s + 1 bits. On an s bit computer the overflow, last carry, bit is discarded. Therefore, on an s bit computer

s 0's

m + m = 0 =0000 ? ? ? 0000

Consider this example. Let m = 227 which when written as an unsigned binary number, is 1100 0111. To write m as a signed binary number, append a leading 0 so that

+227 = 0 1100 0111

1. 161 1010 0001 2. 1010 0001 0 1010 0001 3. If m = +161, return 0 1010 0001

else (if m = -161) return 1 0101 1111 The two's complement of a positive integer is a negative integer. The two's complement of a negative integer is a positive integer.

To write 2 = (10)2 requires 2 bits. To write 22 = (100)2 requires 3 bits. To write 28 = (1000)2 requires 4 bits.

cse 1400 applied discrete mathematics conversions between number systems 5

To write -227, perform the two's complement operation on 0 1100 0111 to get

-227 = 1 0011 1001

Biased Notation for Integers

Biased notation is an alternative method used to represent signed integers. Biased notation represents an integer n as

nb = n + b

where b 0 is called the bias or excess. Adding a bias b to an integer n translates it to the right giving it a a new name. To compute the value n of a biased integer nb, solve the equation nb = n + b for n = nb - b, that is, subtract b from nb.

For illustration, we'll use 8 bit strings .

(b7b6b5b4 b3b2b1b0)b=127

Each bi is either a 0 or a 1 for each i = 0, . . . , 7. Using a bias of b = 127 the 256 integers from -127 to 128 are named 0 to 255. For instance, consider the biased number

(1111 1100)b=127 = nb = n + b = (1111 1100)2 + 127

Horner's rule converts the binary number (1111 1100)2 to 252.

For instance, pick a bias b = 32, and notice the integers from n = -32 to n = 31 map to biased integers from n32 = 0 to n32 = 63.

Let n = -37 and let the bias be b = 127. Then the biased number (-37)127 = (n)b = n + b = -37 + 127 = 90 is the biased name for the value -37.

The subscript b = 127 is a hint to interpret the bit string as biased number with bias b = 127. Drop it when this is clear from context. The diagram show the integers from -127 to 128 along the top line. The bottom line shows the biased numbers 0 to 255 which are used to name integers from -127 to 128.

-127

128

Horner's Rule

111 1 1 1 0

0

2 6 14 30 62 126 252

1 3 7 15 31 63 126 252

0

255

Subtract the bias b = 127 from n + b = 252 to get n = 125 as the value of the biased number

(1111 1100)b=127 = 125

Biased notation is used to encode positive and negative exponents in floating point notation. That is, let

t = ?1. f ? 2eb

be a normalized floating point number. The exponent eb is a biased integer. As a small example, the bias could be b = 4 and exponents from e4 = 0 to e4 = 7 represent values -4 to 3.

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download