675.232 Computer Systems



ENGSCI 232 Computer Systems 2005

Lab 3: Number Representation

Your name: _________________ ID: ____________

Aim

The aim of this project is to develop familiarity with the way variables are stored in memory. You should understand the practical consequences of the numerical representation techniques, and also develop an appreciation of the relationship between programming ideas and computer memory. The representations covered in this lab are those used by Visual Basic, Delphi, and other PC-based systems.

Assignment Due 9:00am Wednesday August 17

You should submit, on this handout, answers to all numbered questions. The questions marked Tricky are probably best left until the end as they are harder!

Overview

You will be running the program MemView that allows values for variables to be entered, and shows how these values are stored, and what happens if you interpret that storage as a value. You will probably be familiar with storage of unsigned integer values, eg 0…255 using 1 byte. However, signed and real values such as -1, -128, and 2.5 may be new to you.

Binary and Hex

Because we have 10 fingers, we normally deal with numbers in base 10 with digits 0, 1, 2, …, 9. For example, when we write 1234 we mean 1*103 + 2*102 + 3*101 + 4*100, and 56.7 means 5*101 + 6*100+ 7*10-1.

Computers work with voltages (not fingers!) to store values in memory. Typically 2 voltages are used, being +5V and 0V. We represent these two voltages as binary-valued ‘bits’. Each bit can be either 0 or 1, where 1 means +5V, and 0 means 0V. To understand how the computer stores values, we need to think in binary terms.

Binary numbers are base 2, with the digits being just 0 and 1. For example, 10112 means 1*23+0*22+1*21+1*20 . Its sometimes convenient to think in hexadecimal (hex). Hexadecimal numbers are base 16 (4 bits gives 24=16), with digits 0, 1, 2, …, 8, 9, A, B, C, D, E, F, where A=10, B=11, …, F=15. The value stored in 8 bits (one byte) can now be written using a 2-digit hexadecimal number. For example, the hexadecimal number AB16 (1 byte) gives 10*161 + 11*160 = 10*16+11 = 171, while 123416 (2 bytes) is the value 1*163 + 2*162 +3*161 + 4*160 = 4660. Table 1 shows a sample of values in binary and hexadecimal.

We note that a byte has 8 bits, and so a byte can store a number between 0 and 255 (256 different bit patterns). Thus, a byte must contain one of the 256 possible values:

0000 00002 = 0016 = 0,

0000 00012 = 0116 = 1,

…,

111111102 = FE16 = 254,

111111112 = FF16 = 255.

The comments above apply only if you are thinking about positive integers. (We call these values ‘unsigned’ because they do not have a + or – sign.) As we’ll see soon, coming up with a system that lets us store both positive and negative integers is a bit more complex.

Notation

When referring to the representation of a value, you may wish to refer to the bits used to represent the value, and possibly collections of these bits. To do this, you should number all bits from 0 with bit 0 being the rightmost (least significant) bit, eg a byte x is 8 bits, written x=x7x6x5x4x3x2x1x0. You can use notation such as x9x8x7x6 to refer to the (unsigned) value corresponding to bits 9 to 6. Eg, if x=101101010012, then x9x8x7x6=01102=6.

Starting Up

Start by running the MemView program. This program is available on the lab PCs under Start : Programs : Other, and also under the Computer Systems pages at esc.auckland.ac.nz/teaching/engsci232sc

The program shows 3 different ways a computer can store numbers:

• storage of a 2’s complement signed integer i (2 bytes of memory),

• storage of a single floating point number x (4 bytes of memory), and

• storage of a double floating point number y (8 bytes of memory).

In each case, the first box allows you to enter a number you want to store. The hex and binary boxes show you two views of what is actually stored in the bytes of memory. The memory can be changed directly by editing the binary or hex values. The ‘Result’ box shows what you get back if you read the signed integer, single or double back from memory.

You may wish to use the built-in Windows calculator for some calculations. You will probably want to switch the calculator to scientific mode as shown in the adjacent figure.

2’s Complement Integers

To allow storage of both positive and negative (ie signed) integers, the computer uses a representation known as “2’s complement”. Whenever we read a value back out of memory, we interpret it as using this 2’s complement convention. This convention is a bit more complicated than the table for unsigned numbers given above. Use the integer entry section of the program to complete the following exercises and answer the questions.

Exercise An integer is stored using two bytes. There are thus 65536 different values that can be represented. By directly entering values to be stored in memory (and using the +1, –1, *2 and /2 buttons to change what is stored), complete the following table to determine the 2’s complement values that are returned in ‘Result’ for each of the 65536 different values we can store. Use this to help you answer the following questions.

|Data stored in memory |Interpretation as a 2’s complement integer (given in |

|(2 bytes = 16 bits of storage) |‘Result’) |

|0000 0000 0000 00002 = |00 0016 = |0 | |

|0000 0000 0000 00012 = |00 0116 = |1 | |

|0000 0000 0000 00102 = |00 0216 = |2 | |

|… | | | |

|0111 1111 1111 11102 = |7F FE16 = |32766 | |

|0111 1111 1111 11112 = |7F FF16 = |32767 | |

|1000 0000 0000 00002 = |80 0016 = |32768 | |

|1000 0000 0000 00012 = |80 0116 = |32769 | |

|… | | | |

|1111 1111 1111 11102 = |FF FE16 = |65534 | |

|1111 1111 1111 11112 = |FF FF16 = |65535 | |

|Binary view of memory |hex view |unsigned decimal view | |

| |of memory |of memory | |

Exercise The electronics used to add numbers will ‘wrap around’ so that adding 1 to 65535 gives 0. Thus, we can think of the unsigned values forming a closed circle as shown below. By adding values outside the circle below, show the 2’s-complement signed values associated with each of the unsigned values shown. Observe that the position (and hence value) of –1, -2 etc is very natural in this view.

[pic]

Exercise What you need to do at the bit level to multiply a number by 2? Give your answer as a new bitwise expression assuming the number being multiplied is stored in bits x15x14…x4x3x2x1x0.

Exercise Explain what you need to do at the bit level to divide by 2 a number stored in bits x15x14…x4x3x2x1x0 You should keep only the integer part, discarding any remainder. Your method should work for positive numbers and even negative values. (Odd negative values and zero are trickier and so don’t need to be included.) Give your answer as a bitwise expression.

Question In a year 4 project running in 1997 in association with Cogita Business Systems, a set of sales figures were received from the company with the following values.

20000, 19194, 19335, 19538, 29213, 24637, 16975, 23341,

15451, 24454, 32760, -32595, -32143, 31067, 22348, 28160

Explain what has gone wrong in the extraction of these values from the database systems, and give the corrected values. Hint: Look at the circle above.

Exercise We can add 2’s complement numbers by treating them as if they were unsigned. The following examples show this at work for 16-bit integers. As part of the addition process, we will generate a “carry” bit C, where C=1 if the addition has given a ‘carry’ into a 17th bit. (Normally C=1 would imply an overflow. However, when adding 2’s complement numbers, the test for overflow is not so simple.) In the following examples, you can use MemView to get and interpret 2’s complement values. You will need to do the binary additions by hand or using the Windows calculator.

Example 1 (C = carry) completed for you

|Decimal |C |16 bit 2’s complement Binary |

| 12345 | |0 |

| 12345 | |0 |

| -12345 | | |

| 32767 | | |

| | | |

|-32| | |

|768| | |

If the bits stored in memory are given by x31x30…x1x0, then this represents the single precision floating point value given by

value = (-1)x31(1+2-1x22+2-2x21+…+2-23x0)(2(x30x29x28…x23-127)

where x30x29x28…x23 denotes the unsigned value represented by bits x30x29x28…x23.

To make sure you understand the single point representation, complete the following examples, using MemView to check your answer. These examples show how to convert a stored bit pattern x31x30…x2x1x0 into a single point value.

Example 1 already completed for you

|x31|x30 |x29 |

sign from x31 (+ or (): +

unsigned exponent value x30x29…x23 (in decimal) =27+20=128+1=129

exponent value interpreted using “excess 127”: e = 129-127=2

significand value 1.x22x21x20 … x1x0 (in decimal) = 1+2-4=1+0.0625=1.0625

Single point value = +1.0625 * 22=1.0625*4=4.25

Example 2

|x31|x30 |x29 |

sign from x31 (+ or ():

unsigned exponent value x30x29…x23 (in decimal) =

exponent value interpreted using “excess 127”: e =

significand value 1.x22x21x20 … x1x0 (in decimal)=

Single point value=

Example 3

|x31|x30 |x29 |

sign from x31 (+ or ():

unsigned exponent value x30x29…x23 (in decimal) =

exponent value interpreted using “excess 127”: e=

significand value 1.x22x21x20 … x1x0 (in decimal)=

Single point value=

The numbers above follow the normal single-point rules. However, the IEEE system also allows for other non-standard values.

Question Thinking about the 1.d1d2…d23*2e representation, what difficulty is there in choosing values for d1d2…d23 and e when storing zero?

Question How are the values +0 and -0 actually stored in memory?

Storage for +0:

|x31|x30 |x29 |

Storage for –0:

|x31|x30 |x29 |

Note: The value “-0” is stored as –0, but displayed simply as 0.

Question What does the computer store if you calculate the following? Try these calculations in your head first. Then use the divide and times buttons to get the computer to do the calculations. (Hint: In MemView, you can directly enter any of the special codes you discover by just keying them in. Most programs do not allow this.)

1/0:

-1/0:

1/(:

-1/(: (be careful – check the storage!)

(/(:

(*20:

(/20:

(1/0*0)*10:

0*(:

0/0:

Question In the tables below, show the binary representations used for these special values.

Special Code “INF”

|x31|x30 |x29 |

Question: Does the sign bit matter for INF? Y/N

Special Code “NAN”

|x31|x30 |x29 |

Note: The sign bit is ignored for NAN; there is no concept of –NAN.

Question Complete the following:

The case of putting the exponent bits x30 x29 x28 x27 x26 x25 x24 x23=11111111 is reserved for representing the special values NAN and (INF. Hence, the largest unsigned exponent value available for storing actual floating point values is:

Largest usable unsigned exponent value x30x29…x23 (in decimal) =… Largest exponent value interpreted using “excess 127”: e=…

Question Using results from above, what is the largest positive value that can be stored? Give both the binary representation and the decimal value. Hint: You can enter numbers such as 1.2E5, meaning 1.2x105. You should set the bits manually to get the right bit storage.

|x31|x30 |x29 |

Largest single point value =

Exercise By completing the following, show the binary representation that would give the smallest positive normalised value. The case of x30 x29 x28 x27 x26 x25 x24 x23= 00000000 is reserved for the special case of representing zero, and so you cannot use this value. Remember that normalised numbers must start “1.something”. Beware that smaller values can be stored in Memview by breaking the normalization rules; we see this next. At this stage, we want to stay with normalized numbers.

|x31|x30 |x29 |

sign from x31 (+ or (): +

smallest unsigned exponent value x30x29…x23 (in decimal) =

smallest exponent value interpreted using “excess 127: e=

significand value 1.x22x21x20 … x1x0 (in decimal) =

Single point value =

Exercise The representation can actually store smaller values by abandoning the “1.something” rule on normalisation, and storing numbers that start 0.1, 0.01 0.001, etc. By starting with the smallest normalized value found above and then using repeated “(2” operations in MemView, work out the actual smallest positive value (in decimal) that can be stored. Give its binary representation.

|x31|x30 |x29 |

sign from x31 (+ or (): +

special value stored in x30x29…x23 to signify a non-normalised value (in decimal) =

Note: this special exponent value is interpreted as: e=-126

smallest special un-normalised significand value 0.x22x21x20 … x1x0 (in decimal) =

Single point value =

Exercise Tricky: Complete that following table that describes how to decode a floating point single-precision number into the appropriate value for that representation. This will take some careful thinking to pull together all your answers for the above questions. Be sure to handle NAN, (INF, (zero, and the non-normalised numbers.

Let s = x31, u=unsigned exponent =(x30x29…x23), v=(x22x21…x0)

|Condition |Decoded Value |

|0 < u < 255 |(-1)s * 2(u-127) * (1.v). |

|u=0, v0 | |

|u=0, v=0 | |

|u=255, v0 (eg v=111 1111 00..00) | |

|u=255, v=0 | |

Doubles

Answer the following questions for the double-precision real numbers. Double precision numbers follow the same rules as single precision numbers, but use more bits.

Question How many bytes does a double use?

Question Which bits, and how many, are used to store the significand? (Remember bits are numbered …x4x3x2x1x0)

Question Which is the sign bit s?

Question Which bits, and how many, are used to store the exponent?

Question The single floating point representation used “excess 127” exponents. Complete the following. Hint: Try storing 1=1.0*20

Doubles use “excess ……..” for their exponent.

Question What is the largest positive value that can be stored? Hint: You can enter numbers such as 1.2E5, meaning 1.2x105. Be exact (and use decimal notation).

-----------------------

[1] Leave tricky parts until after the lab

-----------------------

|Unsigned Decimal|Hex |Binary |

|0 |0 |0 |

|1 |1 |1 |

|2 |2 |10 |

|3 |3 |11 |

|4 |4 |100 |

|5 |5 |101 |

|6 |6 |110 |

|7 |7 |111 |

|8 |8 |1000 |

|9 |9 |1001 |

|10 |A |1010 |

|11 |B |1011 |

|12 |C |1100 |

|13 |D |1101 |

|14 |E |1110 |

|15 |F |1111 |

|16 |10 |1 0000 |

|17 |11 |1 0001 |

|18 |12 |1 0010 |

|19 |13 |1 0011 |

| | | |

|252 |FC |1111 1100 |

|253 |FD |1111 1101 |

|254 |FE |1111 1110 |

|255 |FF |1111 1111 |

|256 |1 00 |1 0000 0000 |

|257 |1 01 |1 0000 0001 |

| | | |

|32765 |7F FD |111 1111 1111 1101 |

|32766 |7F FE |111 1111 1111 1110 |

|32767 |7F FF |111 1111 1111 1111 |

|32768 |80 00 |1000 0000 0000 0000 |

|32769 |80 01 |1000 0000 0000 0001 |

|32770 |80 02 |1000 0000 0000 0010 |

| | | |

|65535 |FF FF |1111 1111 1111 1111 |

|65536 |1 00 00 |1 0000 0000 0000 0000 |

|65537 |1 00 01 |1 0000 0000 0000 0001 |

Table 1: Values in (unsigned) decimal, hex and binary

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

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

Google Online Preview   Download