Laboratory: Integer Representation
CSC 105 - The Digital Age

Goals:

This laboratory exercise provides practice with

• experimenting with the representation of integers,
• comparing capabilities of 16-bit signed integers and 32-bit signed integers, and
• determining what happens when the maximum size of integers is obtained.

Preliminaries

This lab utilizes a program for processing integer values, called integer-rep. To prepare for the lab:

• Open a terminal window.
• You may have a directory named 105 within your home directory, which you created in a previous laboratory session. Use the command ls to determine whether that directory exists. If it does exist, go to the next step. If it does not, create it by entering the following mkdir command in your Terminal command line, as shown below:
mkdir 105
• Move to the 105 directory by entering the following in the Terminal:
cd 105
• Copy the program for this lab into your 105 directory with (note the dot at the end is important):
cp ~walker/c/fluency-book/integer-rep .

Integers and Their Representation

In class we discussed how positive integers are stored within a computer. This lab asks you to apply your understanding of this and experiment with both positive and negative integers, as observed on a computer.

The program integer-rep is written in the C programming language. In this language (and in most others), integers are stored using the fixed-size-storage approach.

The program keeps track of two integers −− one represented in 16 bits and one represented with 32 bits. At the start, each of these integers has the value 1, and integer-rep prints each out in both decimal and binary notation. The program then allows you to perform various operations on these numbers. After each operation, integer-rep prints the new values of these numbers.

1. In a terminal/command window, run the program with the command:

./integer-rep
Note that the leading characters ./ tell the computer to look in the current directory for the program.

Take a careful look at the output the program has printed in your terminal window. You should be able to find both decimal and binary notations for each of two numbers (both of which currently have the value 1).

1. Type "A" into the program and press enter to add 1 to the initial integer values. Then enter "A" a second, and a third, time. (When starting with the value 1, the integers will become 2, 3, and 4.)

Review the binary representation of each integer, and make sure you understand why it has the given binary representation.

2. Use the "M" option 3 times, each time multiplying the values by 2. The integers will become 8, 16, and 32. Again, make sure you understand why the binary representation of each integer looks as it does.

3. Use the "I" option to set the values to 9. Explain the binary representation that results.

4. Use the "I" option to set the values to 32. Then use the "M" option several times to multiply by 2 to obtain the values 64, 128, 256, 512, 1024, 2048, 4096, 8192, and 16384. Explain how the pattern of 0's and 1's obtained changes as you go from one of these numbers to the next.

Now that you have some experience with non-negative integers, we will look at a few negative numbers. (Even though we have not yet discussed the storage of these values in class, you can still make some observations.)

1. Use the "I" option to set the program's values to -1, and describe the binary representation that you see.

2. Use the "M" option to multiply the program's values by 2 several times to obtain the values -2, -4, -8, -16, ..., -8192, -16384, -32768. Can you describe a pattern in the 0's and 1's obtained for these numbers?

3. Have you already formed a hypothesis about the meaning of the initial (leftmost) bit in the fixed-size-storage approach for integers? If so, what is it? If not, use the "I" option to enter several more negative integers and several more positive integers. Then use your observations to form such a hypothesis.

4. Use the "I" option to enter -32768 again. Then use the "S" option to subtract 1 from -32768. What result do you get with the 16-bit integer form and with the 32-bit integer? Are these results what you expected? What do they have in common, and what is different? Try to explain why you get each result.

5. Use the "S" option a few more times to observe the results. Given the current value in each integer, does each subtraction give the expected result?

6. Now use the "A" option several times, each time adding 1 to your previous result. What can you conclude about the maximum integer that can be stored in 16 bits (assuming, as this program does, that we also allow negative numbers)?

7. Use a similar approach to find the maximum integer that can be stored in a 32-bit (signed) integer. Explain your result and how you got it.

8. Read the news account of the computer-related difficulties that grounded all of Comair's flights on December 25, 2004. The article states that the computer system for Comair "has a hard limit of 32,000 changes in a single month." Other articles related this problem to a field in a database that was designed as a 16-bit integer. (Apparently, each change to the crew schedule is stored permanently in a database. It is typical that each database record has an "id" field that is essentially a counter (i.e., the sixth change is likely to be stored with "id"=6.)

1. What do you think was the real (not rounded) limit for changes to crews at Comair?

2. Hypothesize what troubles might have occurred in the software when that limit was reached.

3. From what you know about the fixed-storage-approach for storing integers, can you suggest a way this problem could have been avoided?

For those with extra time

Extra 1

You now know the largest number that the computer stores using 16 bits and have seen some negative numbers also. Experiment with the initialize ("I"), add ("A") , and subtract ("S") options of the integer-rep program to see if you can determine more precisely how negative numbers are represented.

How is the binary representation for -1 related to that of 0? What would happen to the binary representation of -1 if you added 1 to it (using binary addition)?

How is the binary representation for -2 related to that of -1? What would happen to the binary representation of -2 if you added 1 to it (using binary addition)?

Extra 2

Experiment with addition of negative and positive numbers. That is, choose a negative and a positive number that can both be represented in 16 bits. (You might choose two you've seen the integer-rep program display.) What is the result when you add their binary representations using binary addition? Does it agree with their decimal sum?

Try to explain the reason for your result.

Extra 3

Experiment with the addition of two negative numbers between -16384 and -32768. What is the result when you add their binary representations using binary addition? Does it agree with their decimal sum?

Try to explain the reason for your result.

Extra 4

Experiment with the addition of two positive numbers between 8192 and 16384. What is the result when you add their binary representations using binary addition? Does it agree with their decimal sum?

Try to explain the reason for your result.

Created: Henry Walker, January 14, 2005
Revised: Henry Walker, February 16, 2005
Revised: Marge Coahran, February 4, 2008

Revised: Jerod Weinman, February 9, 2011