This laboratory exercise provides practice with
This lab utilizes a program for processing integer values, called integer-rep. To prepare for the lab:
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
cd 105
cp ~walker/c/fluency-book/integer-rep .
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.
In a terminal/command window, run the program with the command:
./integer-rep
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).
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.
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.
Use the "I" option to set the values to 9. Explain the binary representation that results.
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.)
Use the "I" option to set the program's values to -1, and describe the binary representation that you see.
Use the "M" option to multiply the program's values by 2
several times to obtain the
values
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.
Use the "I" option to enter
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?
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)?
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.
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.)
What do you think was the real (not rounded) limit for changes to crews at Comair?
Hypothesize what troubles might have occurred in the software when that limit was reached.
From what you know about the fixed-storage-approach for storing integers, can you suggest a way this problem could have been avoided?
Review your experiments and write a paragraph summarizing your observations.
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)?
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.
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.
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.