Chapter 6 DATA Representation Computer Arithmetics PDF

Preview

Summary

Data Representation...

Description

CHAPTER 6: DATA REPRESENTATION WITHIN THE COMPUTER/NUMBER SYSTEMS, BASE CONVERSIONS AND COMPUTER DATA REPRESENTATION Data Representation 2. Numbering Systems Today, most operating systems, programming languages and hardware devices make the underlying assumption that sophisticated users are familiar with how information is stored in a computer. Without this knowledge, anything other than very basic use of a computer is impossible, as is understanding of many of the fundamental design concepts of digital computers. We use the decimal numbering system, also known as base 10. The decimal system appears to have evolved naturally because we have ten digits on our hands. In decimal, a numeric quantity is represented by a series of digits from 0 to 9. Decimal is also a positional numbering system, whereby the rightmost digit represents a number of units. The digit to the left of that represents the number of tens of units, the next number to the left is the number of tens of tens of units (=hundreds of units), the next is the number of tens of tens of tens of units (=thousands of units), and so on. The actual quantity expressed by the number is the sum of all these quantities. Decimal 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

Octal 1 2 3 4 5 6 7 10 11 12 13 14 15 16 17 20 21 22 23 24 25

Hexadecimal 1 2 3 4 5 6 7 8 9 A B C D E F 10 11 12 13 14 15

Binary 1 10 11 100 101 Think about how you count 110 111 1000 1001 1010 1011 1100 1101 1110 1111 10000 10001 10010 10011 10100 10101

We normally count in decimal. We have 10 symbols from 0 up to 9. If you’re counting when you run out of symbols, you go back to 0 but you put 1 in the next column to remind yourself It ishave easier to convert that you’ve used a whole group once. When you get to 9 again you to go back to 0from againbinary to octal or hexadecimal than to but you increase the 1 in the next column by 1, and so on.

decimal!

Example: Decimal number 3450 Page 1 of 14

3 4 5 0 / | | \ / | | Zero single items / | Five groups of ten items / Four groups of ten groups of ten items Three groups of ten groups of ten groups of ten items Any number other than 10 can be used as the base in which numbers are represented (i.e. there is nothing special about humans usually having ten fingers). Binary What if we had only 2 symbols (0 and 1)? What would come after 1? What about after 101? What about after 1011? What about after 11101? This is the binary system. For example, if we had been born with one finger on each hand (two fingers in total), we might count in binary (or base 2). Here each digit would range from 0 to 1, and each successive digit from right to left would represent the number of pairs of what the previous digit represented.

Example: binary 1101 is the same as decimal 13 Binary number 1 1 0 1 / | | \ / | | One single item (= one item) / | Zero groups of two items (= none) / One group of two groups of two items (= four) One group of two groups of two groups of two items (= eight) Eight plus four plus one is, in decimal, 13. Octal number What would we do if we had only 8 symbols for counting ( 0-7). We would be using the octal system. Look at the octal system above and see if you can work out what number would come after 27. Hexadecimal What would we do if we had 16 symbols (0123456789ABCDEF)? This is called hexadecimal. What number comes after the last one F? Computers naturally use binary for storing numbers. Programmers often use Hexadecimal because it is easier to read and write and easy to convert to and from binary.

Page 2 of 14

Converting Between Bases/ Number Conversion To convert a binary number to a decimal number you must first understand what each digit in the binary number means. E. g. 247. The '2' in 247 represents two hundred because it is a two in the hundreds position (two times a hundred is two hundred). In similar fashion, the '4' in 247 represents forty because it is a four in the tens position (four times ten is forty). Finally, the '7' represents seven because it is a seven in the units position (seven times one is seven). In a decimal number, the actual value represented by a digit in that number is determined by the numeral and the position of the numeral within the number.

When using non-decimal numbering systems, the numeric base should always be mentioned if it is not entirely obvious from the context. Thus 1012 = 510 ,

10110 = 6516 , 10116 = 25710

will not get confused with each other. In the case of hexadecimal (often called simply hex for short), many other styles of identifying this base are used. 101x, 101h, x101 and $101 are all common notations used to reference the hexadecimal number 101. Any number base can be used. Because it is easier and more reliable to design electronic circuits that recognize only two states, "on" and "off", than to design circuits that recognize three or more different states, computers today are based on the binary system. Since any numeric quantity can be represented as a sequence of 0s and 1s, any numeric quantity can be represented as a sequence of "offs" and "ons".

a)

Binary Conversion

i) Binary to decimal It works the same way with a binary number. The right-most position in a binary number is units; moving to the left, the next position is twos; the next is fours; the next is eights; then six teens; then thirty-twos ... Notice that these numbers are all powers of two (base two) - 2^0, 2^1, 2^2, 2^3, 2^4, 2^5. (The units, tens, hundreds, thousands, ten thousands of the decimal system are all powers of ten: (base ten) 10^0, 10^1, 10^2, 10^3, 10^4). So, to convert the binary number 1001 (don't read that as one thousand one - read it as one zero one) to decimal, you determine the actual value represented by each '1' and add them together. The right-most '1' has a decimal value of 1 (it is in the 2^0, or units, position) and the left-most '1' has a decimal value of 8 (it is in the 2^3, or eights, position). So the binary number 1001 is equal to decimal 9. Here's another way to look at it: 1001 ^^^^ | | | |_________> 1 x 2^0 = 1 x 1 = 1 | | |___________> 0 x 2^1 = 0 x 2 = 0 | |_____________> 0 x 2^2 = 0 x 4 = 0 |_______________> 1 x 2^3 = 1 x 8 = 8 --9 Page 3 of 14

A simple way to convert from binary to decimal: Write successive powers of two over each digit from right to left, and add up those numbers under which a 1 appears.

Example: Convert binary 110100 to decimal 32 16 8 4 2 1 1 1 0 1 0 0 32 + 16 + 4 = 52 in decimal A simple way to convert from decimal to binary: Both the decimal system and the binary system are positional number systems. The hexadecimal system is another positional number system. The binary system has only two numerals - 0 and 1; the decimal system has ten numerals: 0,1,2,3,4,5,6,7,8, and 9. In the hexadecimal (or hex) system there are sixteen numerals: 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E, and F. Zero through nine have the same value as a decimal numeral, and A is ten, B is eleven, C is twelve, D is thirteen, E is fourteen, and F is fifteen. The decimal number system is also referred to as "base ten" since each position in a decimal number represents a power of ten - a number that can be written as 10^n, where n is an integer. The binary number system is also referred to as "base two" since each position in a binary number represents a power of two - a number that can be written as 2^n, where n is an integer. The hex number system is also referred to as "base sixteen" since each position in a hexadecimal number represents a power of sixteen - a number that can be written as 16^n, where n is an integer. The right-most position in a hexadecimal number is units; moving to the left, the next position is sixteens; the next is two hundred fifty-sixes; the next is four thousand ninety-sixes, and so on all powers of sixteen - 16^0, 16^1, 16^2, 16^3. A simple way to convert from decimal to binary: Divide the number by two. The remainder (which will be either 0 or 1) is the rightmost binary digit. Divide the quotient by two. This remainder will be the next binary digit to the left. Continue dividing the successive quotients by two and using the remainder as the next binary digit to the left, and stop when the quotient is finally zero. Decimal to binary To convert from decimal to binary, keep dividing the number by 2 and noting down anything that is leftover each time until you finally get 0 and a leftover. Then read the number out from the bottom up. Any time you do one of those calculations, do it the opposite way immediately after to check that you get your original number back again – then you know you did it right. Have a go at this: Convert 11101 to decimal, and then convert it back from decimal to binary again (to get 11101 of course).

Page 4 of 14

Example

base 2 2 2 2 2 2 2

decimal leftovers 21 10 1 5 0 2 1 1 0 0 1 21 = 10101

Example: Convert decimal 52 to binary 52 26 13 6 3 1

/ / / / / /

2 2 2 2 2 2

= = = = = =

26 13 6 3 1 0

remainder remainder remainder remainder remainder remainder

0 0 1 0 1 1

------------------| ----------------| | --------------| | | ------------| | | | ----------| | | | | --------| | | | | | | | | | | | The binary equivalent is: 1 1 0 1 0 0

Exercises: Note how the number base is written as a subscript to the number. 1001012 = ?10 000112 = ?10 28710 = ?2 10110 = ?2 ii)

Binary to hexadecimal

To convert a binary number to a hex equivalent, notice that four binary digits together can have a value of from 0 to 15 (decimal) exactly the range of one hex digit. So four binary digits will always convert to one hex digit! it is very simple to convert binary numbers to hexadecimal, and vice versa. Mathematically, because 16 (the number base for hex) is 2 (the number base for binary) raised to the 4th power, there is a direct correspondence between four binary digits and one hex digit. Notice, for example, that the largest 4 digit binary number is 1111, while the largest single hexadecimal digit is F. Both of these, of course, represent the same thing: the decimal number 15. To convert a hex number to binary, you could convert the hex number to decimal, then convert the decimal number to binary. The easy way, however, is to take each hex digit, and replace it with the equivalent 4 digit binary number. To go from binary straight to hexadecimal, group the Page 5 of 14

binary number into groups of 4 digits starting from the RIGHTmost digit. (A few leading zeros may have to be added to the binary number to make this work out properly). Each group of 4 can then be replaced with the corresponding hex digit. The following table summarizes the equivalencies between a hex digit and 4 binary digits. For example: 1 0 1 1 0 1 1 1 from right to left, make four-digit groups \ /\ / \ / \ / eleven seven determine the decimal equivalent of each | | group V V B 7 write the equivalent hexadecimal digit

Example: Convert binary 11100000100001 to hex 0011 1000 0010 0001 3 8 2 1 The hex equivalent is 3821 Note in the last example how the binary digits were grouped from the right to the left, making it necessary to pad with two leading zeros. Hexadecimal, used as a shorthand for binary, is particularly useful because on most machine a byte is eight bits (each "binary digit" is called a bit) long. Thus, one byte of data can be represented by exactly 2 hex digits, which is much more compact than 8 binary digits. (Four bits, which can be represented by exactly one hex digit, is often called a nibble). Some older devices (for example, calculators from a few years ago) do not have the letters A, B, ... F, but only have the digits 0 through 9. For this reason, octal (base eight) has occasionally been used as a shorthand for binary. iii)

Hex to decimal

What is the decimal equivalent of B7 hex? B7 ^^ | |_________> 7 x 16^0 = 7 x 1 = 7 |___________> 11 x 16^1 = 11 x 16 = 176 --183 decimal Check that against the decimal equivalent of 10110111 binary: 10110111 ^^^^^^^^ | | | | | | | |_________> 1 x 2^0 = 1 x 1 = 1 | | | | | | |___________> 1 x 2^1 = 1 x 2 = 2 | | | | | |_____________> 1 x 2^2 = 1 x 4 = 4 | | | | |_______________> 0 x 2^3 = 0 x 8 = 0 | | | |_________________> 1 x 2^4 = 1 x 16 = 16 | | |___________________> 1 x 2^5 = 1 x 32 = 32 | |_____________________> 0 x 2^6 = 0 x 64 = 0 Page 6 of 14

|_______________________> 1 x 2^7 = 1 x 128 = 128 --183 decimal Example: Convert hexadecimal A40D to binary A 4 0 D 1010 0100 0000 1101 The binary equivalent is 1010010000001101 iv. Octal to binary Eight is two to the third power, and so three binary digits are equivalent to one octal digit in the same way that four bits are equivalent to one hex digit. The advantage of octal is that it only uses the digits from 0 to 7, and so can be implemented on devices that don't support the alphabet. The main disadvantage to octal is that a byte (on most machines) works out to be exactly two and two thirds octal digits long (3 bits plus 3 bits plus 2 bits), which can be awkward at times. On the old DEC-20 (one of DEC's pre VAX minicomputers, which had 9 bit bytes), however, octal was more convenient than hex, since a byte was exactly 3 octal digits long (and an awkward two and a quarter hex digits). Example: Convert octal 570 to binary 5 7 0 101 111 000 The binary equivalent is 101111000 Example: Convert hex A0E to octal Simplest method: Convert to binary, then to octal A 0 E 1010 0000 1110 (regrouping from the right...) 101 000 001 110 5 0 1 6 The octal equivalent is 5016 Example: Convert octal 177 to hex 1 001

7 7 111 111

(regrouping...) 0000 0111 1111 0 7 F The hex equivalent is 7F Note that conversions between octal and hex COULD be done by converting to base 10 as the middle step. Since octal binary and hex to binary conversions are so simple, however, it is much Page 7 of 14

easier to use binary as the middle step. Exercise: Complete the following table Number Base 2 -------

8 -------

10 -------

16 -------

1101 6 71 99 ABC

BINARY OPERATION A) ADDITION Binary addition is the simplest of the binary operations, so let's start there. To add two binary numbers, you only need to know three things: 0 + 0 is 0 carry 0 (pretty easy) 0 + 1 is 1 carry 0 1 + 1 is 0 carry 1. The rest of the operation is just as in base ten.

Example: Binary subtraction; 100011 - 110 1 1 0 0 0 1 1 borrow 1 0 0 0 0 1 1 borrow 1 -110 ---> -110 ---> --------------------01 01 11 0 1 0 0 1 1 borrow 1 011011 -110 ---> -110 --------------------01 11101 For example, let's add 1010 (10 in base ten) and 1011 (11 in base ten). 1010 + 1011 ---10101 = 1x24 + 0x23 + 1x22+0x21 + 1x20 = 1x16 + 0x8 + 1x4 +0x2 +1x1 = 16 + 0 + 4 + 0 + 1 = 21 i. e. 0 + 1 is 1 carry 0 1 + 1 is 0 carry 1, 0 + 0 + 1 (carried over) is 1 carry 0 1 + 1 is 0 carry 1 Page 8 of 14

1 + 0 is 1 carry 0 so the final sum is 10101, 21 in base ten, which is correct. MULTIPLICATION For multiplication you just have to remember that 1 times a number is that number and 0 times a number is 0. Once you have all of the little multiplications done, you add up the products. Let's try multiplying 101 (5) and 10 (2): 101 x 10 ---From the bottom right, 0 times 101 is 0 (because that is the product of any number and zero) and 1 times 101 is 101 moved over 1 column to the left (because the 1 was moved over one column to the left), giving 0 plus 1010, or 1010, which is in base 10 is 10, and correct. SUBTRACTION This is just like regular subtraction, with borrowing. Let's try 1101 (13 in base 10) minus 110 (6 in base 10): 1101 - 110 ---From the right, 1 minus 0 is 1. Next, 0 minus 1 is impossible, so you borrow from the next number to the left, making the full top number 10(10)1; then 10 minus 1 is 1. Next 0 minus 1 is impossible again, so we go through the same thing, making the number 0(10)01, and 10 minus 1 is again 1. Thus the final result is 111, or 7 in base 10, which is correct. DIVISION This is mostly trial and error. First you take the first digit of the number you are dividing and see whether the number you are dividing into it goes in (in other words is greater than the number you are dividing by, because in base 2, if it goes in more than once, the previous step must have been incorrect). If it does, great - you can move on to the next digit by itself; if it doesn't go in, see whether the number goes into the first two digits. Keep going on like this until it does go in. Let's divide 10110 (22) by 111 (7). First, see if 111 goes into the first digit, 1. It doesn't, so try the first two. 111 doesn't go into 10 or 101, but it does go into 1011 once, so the first digit of the answer is 1. Now you subtract 111 from the 1011, leaving you with 100, and start over saying "does 111 go into 100?" Since it doesn't, you add the next digit of the number you are dividing: bring down the 0 from the end of 10110 to make the number you divide 1000, which 111 does go into. Subtracting 111 from 1000, we get 1 with 1 left over. 111 does not go into 1 so that is our remainder, and the final answer is 11 remainder 1, which is 3 remainder 1, which is correct. You could also continue this process indefinitely after the decimal point, because 1/7 is a repeating decimal so you will always have a remainder. Non-Decimal Arithmetic Page 9 of 14

Often a programmer has binary or hexadecimal data and needs to do simple arithmetic with it, such as addition or subtraction. One technique is to convert the data to decimal, do the arithmetic, then convert back to the base in question. This will work. But addition, subtraction and multiplication are quite easy to do even in non-decimal bases, so it is usually simpler to do the arithmetic directly. Essentially all you have to remember is that when you carry (or borrow) a 1, you are carrying (or borrowing) 2, 8 or 16 (depending on what base you're working with) and not 10. Example: Hexadecimal addition; A0F + F5 1 A0F F5 ---> --04 carry 1

A0F F5 ---> --4 carry 1

11 A0F F5 --B04

Note that F+5 is 15+5 = 20 (decimal) which is 14 hex. Similarly, F+1 is 15+1 = 16 (decimal) which is 10 hex. Finally A+1 is 10+1 = 11 (decimal) which is B in hex.

Actually, the arithmetic is really being done in decimal, since the decimal addition tables are the only ones that people normally have memorized. It's just that the conversion to decimal and back > again is being done one digit at a time, so it is easier to perform than converting larger numbers. Example: Hexadecimal subtraction; 207 - B6 1 1 2 0 7 borrow 1 1 0 7 1 0 7 - B 6 ---> - B 6 ---> - B 6 ------------1 5 1 1 5 1 Here 7-6 = 1 (sa me in decimal and hex). 0 -B is not pos sible, so 1 is borrowed from the next column, making 10 -B which is 16-11 = 5 ( decimal). 1 was borrowed, leav ing 1 in the leftmost column.

Example: Binary subtraction; 100011 - 110 1 1 0 0 0 1 1 borrow 1 - 1 1 0 ---> ---------- 0 1

0

0 0 0 1 1 borrow 1 - 1 1 0 ---> - ---------0 1

1 1 0 1 0 0 1 1 borrow 1 0 1 1 0 1 1 - 1 1 0 ---> - 1 1 0 ---------- ----------0 1 1 1 1 0 1 If all this borrowing confuses you, try to do a decimal subtraction such as 20005 - 99, ju st to remind yourself how bor rowing actually works.

Exercise: Non decimal arithmetic Hexadeci mal A001 + FFF ----

2B03 -1C00 ----

Octal 724 +555 ----

3301 -277 ----

Binary 1100010 + 1111 -------

1010001 - 111000 -------

163 =4096 Most

162 161 160 =256 =16 =1 . Hexadec.

16-1 16-2 =1/16 =1/256

Page 10 of 14

16-3 =1/4096 Least

Significant

Significant Digit

point

Digit

Hexadecimal to Decimal Conversion e.g. 2AF16 = 2 x (162) + 10 x (161) + 15 x (160) = 68710 Repeat Division: Convert decimal to hexadecimal This method uses repeated division by 16. E.g. convert 37...