Convert to binary using the excess_127 system

Chapter 2 Data Representation AITT 4300 DIGITAL COMPUTER STRUCTURES

PRELUDE TO PROGRAMMING, 6TH EDITION BY ELIZABETH DRAKE

2.1 Decimal and Binary Representation

o The number system we normally use is the decimal system. o It uses 10 as the base. o But a number system can use any base. o Computers work with the binary system (base 2). o Other systems used with computers are octal (base 8) and hexadecimal (base 16).

PRELUDE TO PROGRAMMING, 6TH EDITION BY ELIZABETH DRAKE

Bases and Exponents Any number squared means that number times itself. Example: 10 is the base and 2 is the exponent:

◦ 102 = 10*10 = 100

When a number is raised to a positive integer power, it is multiplied by itself that number of times. Example: the base is 5 and the exponent is 6:

56 = 5*5*5*5*5*5 = 15,625

Exception 1: When a non‐zero number is raised to the power of 0, the result is always 1. ◦ 5,3450 = 1 ◦ 40 = 1 ◦ (–31)0 = 1

Exception 2: 00 is undefined

PRELUDE TO PROGRAMMING, 6TH EDITION BY ELIZABETH DRAKE

The Decimal System

PRELUDE TO PROGRAMMING, 6TH EDITION BY ELIZABETH DRAKE

The first eight columns of the decimal system

107 106 105 104 103 102 101 100

10,000,000 1,000,000 100,000 10,000 1,000 100 10 1

ten‐millions millions hundred‐ thousands

ten‐thousands thousands hundreds tens ones

Expanded Notation

The ten digits that are used in the decimal system are 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. Any number in the decimal system can be written as a sum of each digit multiplied by the value of its column. This is called expanded notation. The number 6,825 in the decimal system actually means:

5*100 = 5*1 = 5

+ 2*101 = 2*10 = 20

+ 8*102 = 8*100 = 800

+ 6*103 = 6*1,000 = 6,000

6,825

Therefore, 6,825 can be expressed as: 6*103 + 8*102 + 2*101 + 5*100

PRELUDE TO PROGRAMMING, 6TH EDITION BY ELIZABETH DRAKE

The Binary System

The binary system follows the same rules as the decimal system. The difference is that the binary system uses a base of 2 and has only two digits (0 and 1). The rightmost column of the binary system is the one’s column (20). It can contain a 0 or a 1. The next number after one is two; in binary, a two is represented by a 1 in the two’s column (21) and a 0 in the one’s column (20) ◦ one‐hundred in decimal is represented by a 1 in the one‐hundred’s (102) column and 0s in the ten’s column (101) and the one’s column (100)

◦ in binary, a 1 in the 22’s column represents the number 4; i.e. 100

PRELUDE TO PROGRAMMING, 6TH EDITION BY ELIZABETH DRAKE

The Binary System

PRELUDE TO PROGRAMMING, 6TH EDITION BY ELIZABETH DRAKE

The first eight columns of the binary system

Power of 2 27 26 25 24 23 22 21 20

Decimal value 128 64 32 16 8 4 2 1

Binary representation

PRELUDE TO PROGRAMMING, 6TH EDITION BY ELIZABETH DRAKE

Converting the Decimal Number 2910 to Binary 29 is less than 32 but greater than 16 so put a 1 in the 16’s (24) column.

29 – 16 = 13 13 is less than 16 but greater than 8 so put a 1 in the eight’s (23) column

13 – 8 = 5 5 is less than 8 but greater than 4 so put a 1 in the four’s (22) column

5 – 4 = 1 1 is less than 2 so there is nothing in the two’s (21) column Put a 0 in the two’s column You have 1 left so put a 1 in the one’s (20) column Therefore, 2910 = 111012 Power of 2 25 24 23 22 21 20

Decimal value 32 16 8 4 2 1

Binary representation 0 1 1 1 0 1

PRELUDE TO PROGRAMMING, 6TH EDITION BY ELIZABETH DRAKE

Converting the Decimal Number 17210 to Binary There is one 128 in 172 so put a 1 in the 128’s (27) column

172 – 128 = 44 44 is less than 64 so put a 0 in the 64’s (26) column 44 is less than 64 but greater than 32 so put a 1 in the 32’s (25) column

44 – 32 = 12 12 is less than 16 but greater than 8 so put a 0 in the 16’s (24) column and a 1 in the eight’s (23) column

12 – 8 = 4 Put a 1 in the four’s (22) column

4 – 4 = 0 Put 0s in the last two columns Power of 2 2

7 26 25 24 23 22 21 20

Decimal value 128 64 32 16 8 4 2 1

Binary

representation 1 0 1 0 1 1 0 0

Converting Binary to Decimal

To convert a binary number back to decimal, just add the value of each binary column.

Convert the binary number 10112 to decimal o There is a 1 in the one’s column o There is a 1 in the two’s column so the value of that column is 2 o There is a 0 in the four’s column so the value of that is 0 o There is a 1 in the eight’s column so the value of that column is 8

1 + 2 + 0 + 8 = 11 o Therefore, 10112 = 1110

PRELUDE TO PROGRAMMING, 6TH EDITION BY ELIZABETH DRAKE

Convert the Binary Number 101010102 to Decimal

There is a 0 in the one’s column There is a 1 in the two’s column so the value of that column is 2 There is a 0 in the four’s column so the value of that is 0 There is a 1 in the eight’s column so the value of that column is 8 There is a 0 in the 16’s column There is a 1 in the 32’s column so the value of that column is 32 There is a 0 in the 64’s column There is a 1 in the 128’s column so the value of that column is 128

0 + 2 + 0 + 8 + 0 + 32 + 0 + 128 = 170

Therefore, 101010102 = 17010

PRELUDE TO PROGRAMMING, 6TH EDITION BY ELIZABETH DRAKE

2.2 The Hexadecimal System The hexadecimal system uses a base of 16. ◦ there is a one’s column (160)

◦ a 16’s column (161)

◦ a 256’s column (162)

◦ a 4,096’s column (163)

◦ a 65,536’s column (164)

◦ and so forth

Rarely need to deal with anything larger than the 164’s column. The hexadecimal system makes it easier for humans to read binary notation.

PRELUDE TO PROGRAMMING, 6TH EDITION BY ELIZABETH DRAKE

The Hexadecimal System

PRELUDE TO PROGRAMMING, 6TH EDITION BY ELIZABETH DRAKE

The first five columns of the hexadecimal system

Hexadecimal

column 16 4 163 162 161 160

16*16*16*16 16*16*16 16*16 16 1

Decimal

equivalent 65,536 4,096 256 16 1

PRELUDE TO PROGRAMMING, 6TH EDITION BY ELIZABETH DRAKE

Hexadecimal Digits o The decimal system uses 10 digits (0 through 9) in each column (base 10) o The binary system uses two digits (0 and 1) in each column (base 2) o The hexadecimal system uses 16 digits in each column (base 16) o How can you represent 10 in the one’s column in base 16?

o no way to distinguish “ten” (written as 10) from “sixteen” (also written as 10  a one in the 16’s column and a zero in the one’s column)

o Use uppercase letters to represent the digits 10 through 15 o hexadecimal digits are 0 through 9 and A through F

◦ 1010 is represented as A16 ◦ 1110 is represented as B16 ◦ 1210 is represented as C16 ◦ 1310 is represented as D16 ◦ 1410 is represented as E16 ◦ 1510 is represented as F16

PRELUDE TO PROGRAMMING, 6TH EDITION BY ELIZABETH DRAKE

Converting the Decimal Number 2310 to Hexadecimal There is one 16 in 2310 so put a 1 in the 16’s column

 23 – 16 = 7 so put a 7 in the 1’s column

 Therefore, 2310 = 1716

Power of 16 163 162 161 160

Decimal value 4096 256 16 1

Hexadecimal representation 1 7

PRELUDE TO PROGRAMMING, 6TH EDITION BY ELIZABETH DRAKE

Converting the Decimal Number 87510 to Hexadecimal 875 is less than 4,096 but greater than 256 so there is nothing in the 4,096’s (163) column Divide 875 by 256 to see how many 256s there are 875 ÷ 256 = 3 with a remainder of 107 Put a 3 in the 256’s column 107 ÷ 16 = 6 with a remainder of 11 Put a 6 in the 16’s column 11 in decimal notation = B in hexadecimal notation Put a B in the one’s column Therefore, 87510 = 36B16 Power of 16 16

3 162 161 160

Decimal value 4096 256 16 1

Hexadecimal representation 3 6 B

PRELUDE TO PROGRAMMING, 6TH EDITION BY ELIZABETH DRAKE

Converting the Hexadecimal Number 123D16 to Decimal In expanded notation, this hexadecimal number is:

(1*4096) + (2*256) + (3*16) + (D*1)

D in hexadecimal is 13 in decimal, so:

4096 + 512 + 48 + 13 = 4669

Therefore, 123D16 = 466910

Power of 16 163 162 161 160

Decimal value 4096 256 16 1

Hexadecimal representation 1 2 3 D

Using Hexadecimal Notation

Notice:

PRELUDE TO PROGRAMMING, 6TH EDITION BY ELIZABETH DRAKE

Decimal Binary Hexadecimal Decimal Binary Hexadecimal

0 0000 0 8 1000 8

1 0001 1 9 1001 9

2 0010 2 10 1010 A

3 0011 3 11 1011 B

4 0100 4 12 1100 C

5 0101 5 13 1101 D

6 0110 6 14 1110 E

7 0111 7 15 1111 F

PRELUDE TO PROGRAMMING, 6TH EDITION BY ELIZABETH DRAKE

Using Hexadecimal Notation It is common to write a long binary number in hexadecimal notation. The 15 hexadecimal digits represent all combinations of a 4‐bit binary number. Convert the following binary number to hexadecimal notation:

11101010000011112 1. Separate the binary number into sets of 4 digits:

1110 1010 0000 1111 2. Refer to the table, if necessary, to make the conversions

11102 = E16 10102 = A16 00002 = 016 11112 = F16

Therefore, 11101010000011112 is EA0F16

2.3 Integer Representation  How computers process numbers depends on each number’s type.  Integers are stored and processed in quite a different manner from floating point numbers.  Even within the broad categories of integers and floating point numbers, there are more distinctions.  Integers can be stored as unsigned numbers (all nonnegative) or as signed numbers (positive, negative, and zero).  Floating point numbers also have several variations.

PRELUDE TO PROGRAMMING, 6TH EDITION BY ELIZABETH DRAKE

Unsigned Integer Format

 A computer processes information in the form of bytes.  Bytes are normally 8 to 16 bits.  To store 112 and 1011012 both must have the same length as a byte.  Do this by adding 0s to the left of the number to fill up as many places as needed for a byte.  This is called the unsigned form of an integer.

PRELUDE TO PROGRAMMING, 6TH EDITION BY ELIZABETH DRAKE

Unsigned Binary Integers Store the decimal integer 510 in an 8‐ bit memory location:

Convert 510 to binary: 1012 Add five 0s to the left to make 8 bits:

000001012

Store the decimal integer 92810 in a 16‐bit memory location:

Convert 92810 to binary: 11101000002 Add six 0s to the left to make 16 bits:

00000011101000002

PRELUDE TO PROGRAMMING, 6TH EDITION BY ELIZABETH DRAKE

Overflow

If you try to store an unsigned integer that is bigger than the maximum unsigned value that can be handled by that computer, you get a condition called overflow.

Store the decimal integer 2310 in a 4‐bit memory location:  range of integers available in 4‐bit location is 010 through 1510

Therefore, attempting to store 2310 in a 4‐bit location gives an overflow.

Store the decimal integer 65,53710 in a 16‐bit memory location: range of integers available in 16‐bit location is 010 through 6553510

Therefore, attempting to store this number in a 16‐bit location gives an overflow.

PRELUDE TO PROGRAMMING, 6TH EDITION BY ELIZABETH DRAKE

Range of Unsigned Integers

Number of Bits Range

8 0...255

16 0...65,535

32 0...4,294,967,295

64 0...18,446,740,000,000,000,000 (approximate)

PRELUDE TO PROGRAMMING, 6TH EDITION BY ELIZABETH DRAKE

Sign‐and‐Magnitude Format The simple method to convert a decimal integer to binary works well to represent positive integers and zero.

We need a way to represent negative integers.

The sign‐and‐magnitude format is one way.

The leftmost bit is reserved to represent the sign.

The other bits represent the magnitude (or the absolute value) of the integer.

PRELUDE TO PROGRAMMING, 6TH EDITION BY ELIZABETH DRAKE

PRELUDE TO PROGRAMMING, 6TH EDITION BY ELIZABETH DRAKE

Store the decimal integer +2310 in an 8‐bit memory location using sign‐ and‐magnitude format

Convert 2310 to binary: 101112 Since this is an 8‐bit memory location, 7 bits are used to store the magnitude of the number.

101112 uses 5 bits so add two 0s to the left to make up 7 bits: 00101112 Finally, look at the sign. This number is positive so add a 0 in the leftmost place to show the positive sign.

Therefore, +2310 in sign‐and‐magnitude format in an 8‐bit location is 000101112

PRELUDE TO PROGRAMMING, 6TH EDITION BY ELIZABETH DRAKE

Store the decimal integer -1910 in a 16‐bit memory location using sign‐ and‐magnitude format

Convert 1910 to binary: 100112 Since this is a 16‐bit memory location, 15 bits are used to store the magnitude of the number.

100112 uses 5 bits so add ten 0s to the left to make up 15 bits: 0000000000100112 Finally, look at the sign. This number is negative so add a 1 in the leftmost place to show the negative sign.

Therefore, ‐1910 in sign‐and‐magnitude format in an 8‐bit location is 10000000000100112

PRELUDE TO PROGRAMMING, 6TH EDITION BY ELIZABETH DRAKE

The Problem of the Zero (a) Store the decimal integer 010 in an 8‐bit memory location using sign‐and‐magnitude format: Convert 010 to binary: 02 Since this is an 8‐bit memory location, 7 bits are used to store the magnitude of the number. The number 02 uses 1 bit so add six 0s to the left to make up 7 bits: 00000002 Look at the sign. Zero is considered a non‐negative number so you should add a 0 in the leftmost place to show that it is not negative. Therefore, 010 in sign‐and‐magnitude in an 8‐bit location is: 000000002 (b) ... but...given that 100000002 is an 8‐bit binary integer in sign‐and‐magnitude form, find its decimal value: First convert the rightmost 7 bits to decimal to get 010 Look at the leftmost bit; it is a 1. So the number is negative. Therefore, 100000002 represents the decimal integer –010

One’s Complement Format

The fact that 0 has two possible representations in sign‐and‐magnitude format is one of the main reasons why computers usually use a different method to represent signed integers. There are two other formats that may be used to store signed integers. The one’s complement method is not often used, but it is explained here because it helps in understanding the most common format: two’s complement. To complement a binary digit, you simply change a 1 to a 0 or a 0 to a 1.

In the one’s complementmethod, positive integers are represented as they would be in sign‐and‐ magnitude format. The leftmost bit is still reserved as the sign bit.

+610, in a 4‐bit allocation, is still 01102 In one’s complement, –610 is just the complement of +610

–610 becomes 10012 The range of one’s complement integers is the same as the range of sign‐and‐magnitude integers. BUT… there are still two ways to represent the zero.

PRELUDE TO PROGRAMMING, 6TH EDITION BY ELIZABETH DRAKE

Store the decimal integer -3710 in an 8‐bit memory location using one’s complement format

Convert 3710 to binary: 1001012 Since this is an 8‐bit memory location, 7 bits are used to store the magnitude

The number 1001012 uses 6 bits so add one 0 to the left to make up 7 bits:

01001012

This number is negative. Complement all the digits by changing all the 0s to 1s and all the 1s to 0s

Add a 1 in the 8th bit location because the number is negative

Therefore, –3710 in one’s complement in an 8‐bit location is 110110102

PRELUDE TO PROGRAMMING, 6TH EDITION BY ELIZABETH DRAKE

Converting One’s Complement to Decimal To convert a one’s complement number back to decimal: Look at the leftmost bit to determine the sign. If the leftmost bit is 0, the number is positive and can be converted back to decimal immediately. If the leftmost bit is a 1, the number is negative. ◦ Un‐complement the other bits (change all the 0s to 1s and all the 1s to 0s) ◦ then convert the binary bits back to decimal ◦ Remember to include the negative sign when displaying the result!

PRELUDE TO PROGRAMMING, 6TH EDITION BY ELIZABETH DRAKE

PRELUDE TO PROGRAMMING, 6TH EDITION BY ELIZABETH DRAKE

The Problem of the Zero Again a) Store the decimal integer 010 in an 8‐bit memory location using one’s complement format:

Convert 010 to binary: 02 Since this is an 8‐bit memory location, 7 bits are used to store the magnitude The number 02 uses 1 bit so add six 0’s to the left to make up 7 bits: 00000002 Zero is considered non‐negative so add a 0 in the leftmost place Therefore, 010 in one’s complement in an 8‐bit location is 000000002 (b) but... given that 111111112 is a binary number in one’s complement form, find its decimal value:

Look at the leftmost bit. It is a 1 so you know the number is negative Since the leftmost bit is 1, all the other bits have been complemented. “un‐complement” them to find the magnitude of the number. When you un‐complement 11111112, you get 00000002 Therefore, 111111112 in one’s complement represents the decimal integer –010

PRELUDE TO PROGRAMMING, 6TH EDITION BY ELIZABETH DRAKE

Why the Fuss About Nothing? Why is there so much fuss about the zero? Why not just define zero in binary as 00002 (or 000000002 or 00000000000000002) and be done with it? In a 4‐bit allocation, the bit‐pattern 11112 still exists. Unless the computer knows what to do with it, the program will get an error. It might even not work at all. One possible scenario: If the result of a calculation using one’s complement was 11112, the computer would read this as –0. If you then tried to add 1 to it, what would the answer be? ◦ The number that follows 11112 in a 4‐bit allocation is 00002. ◦ That would mean, using one’s complement, that –0 + 1 = +0. This certainly would not be an irrelevant issue!