Lab: Binary Representation

This laboratory’s exercises will allow experimenting with the representation of integers and determining what happens when the maximum size of integers is obtained. Download the starter code for this lab integer-rep.tar.gz and extract it with the following commands:

$ mkdir -p csc161/labs/integer-rep
$ cd csc161/labs/integer-rep
$ tar xvzf ~Downloads/integer.tar.gz

A. Positive Integers and Their Representation

Your reading described how positive integers are stored within a computer. This part of the lab asks you to apply your understanding from this reading to positive integers, as observed on a computer.

Examine the source code of both integer-rep.c and integer-rep.scm. In particular look at the section on Menu Options.

integer-rep.c illustrates how integers usually are stored in computers, while the scheme programming language and enviornment uses a variable-size-storage approach. With variable-size-storage, the binary representation does not have a 16-bit or 32-bit form; rather, the binary representation uses as many bits as needed.

The C code you can compile and run in the usual way. The scheme code can be run in a Scheme interpreter by typing the following command into a terminal window:

$ scheme-elk -l integer-rep.scm

Exercises

Driver: Student closer to the whiteboard

1. Compile and run integer-rep.c. When you run it, it initially shows the binary representation of the number 1. Use the operation “A” to add 1 to the values. Then use “A” again, and again, and again. (When starting with the value 1, the integers will become 2, 3, 4, and 5.) Review the binary representation of each integer, and explain why it has the binary representation printed.
2. Use the “I” option to set the value to 12. The use the “M” option 5 times, which will multiply the value by 2 each time to obtain 24, 48, 96, 192, and 384. Explain why the binary representation of each integer looks as it does, including how the pattern of 0’s and 1’s obtained changes as you go from one of these numbers to the next.
3. Try to use the “I” option to set the integer to a 5-digit positive integer (e.g., 10000), a 10-digit positive integer (e.g., 2000000000), a 15-digit positive integer, and a 20-digit positive integer. Explain what happens in each case.
4. Repeat step 1 to determine the binary representations for integers 1, 2, 3, 4, and 5 with the Scheme program. To what extent are these the same or different from the fixed-size-storage approach?
5. Repeat step 3 with the Scheme program. Explain the similarities or differences.

B. Negative integers and Overflows

Check out this news account of computer related difficulties that grounded all of Comair’s flights on December 25, 2004. The computer system for Comair “has a hard limit of 32,000 charges in a single month.” More recently, there was a similar issue caused by a popular YouTube video.

Use the integer-rep.c program and the “I” option to set the program’s values to -1, -2, -3, and -5. Review the 0’s and 1’s to determine whether the computer uses sign-magnitude notation, ones complement notation, or twos complementnotation.

Next, use the “I” option to set the value to -32766. Then use “S” four times to subtract 1. Explore the results do you get with the 16-bit integer compared to the 32-bit integer.

Use the “A” option several times to add 1 to your result of the previous step. Again, observe what you see in the 16-bit integer compared to the 32-bit integer.

Exercises

Driver: Student farther from the whiteboard

1. What can you conclude about the maximum integer that can be stored in 16 bits (assuming the processing is allowed to handle both negative and positive numbers)?
2. Use a similar approach to find the maximum integer that can be stored in a 32-bit (signed) integer.
3. Briefly describe the issues that were encountered by Comair and Youtube (from the beginning of this problem).