Lab 3: Bit Vectors and Floating Point

Introduction

Bit vectors. As you hopefully began to see in lab 2 bit vectors are a useful data type. In this lab, we will do more with bit vectors. See lab 2 or the textbook for a description of bit vectors and bit vector operations (&, |, ^, <<, >>, >>>).

Floating point. Since computers have finite storage space, their representation of real numbers is approximate since some real numbers require an infinite number of digits to represent them (e.g., PI). Worse, computers often use a small number of bits (e.g., 32, 64) to represent floating points; usually the same number of bits or twice the number of bits used to represent integers. This means that some numbers that can be represented with a finite number of bits (but more than 32 or 64 bits) must be also be approximated.

To represent (at least approximately) floating point numbers efficiently we use scientific notation, which allows us to express very small number as well as very large numbers. The formula we use is as follows:

N = (-1)^s * 2^exp-bias * 1.frac

s is a sign flag that determines whether the result is positive or negative. exp is an unsigned (non-negative) integer that along with bias determines how far to move the decimal point to the left (if exp-bias is negative) or the right (if exp-bias is positive). bias is a constant that allows for negative powers of 2, which is needed since exp is unsigned. bias is predetermined based on the number of bits used to represent the exp in the floating point representation. If there are n bits then bias is 2^n-1-1. Finally, frac is the fraction and determines the significant binary digits in the number. Notice that as in scientific notation expressed in decimal, the value is normalized; there is a single 1 to the left of the decimal point. For this reason, the 1 is implicit and is not expressed explicitly in the floating point representation.

In class, we looked at (IEEE) single precision floating point values where the leftmost bit is the sign bit, the next 8 bits are the exponent, and the remaining 23 bits are the fraction, which fit into a 32-bit representation. The bias in this case is 2^8-1-1 or 127. We also talked briefly about double precision floating point values where the leftmost bit is the sign bit, the next 11 bits are the exponent, and the remaining 52 bits are the fraction. The bias in this case is 2^11-1-1 or 1023.

In this lab, we will work with a floating point representation for 8 bits (which will not be all that accurate). The leftmost bit is the sign bit, the next 4 bits are the exponent, and the remaining 3 bits are the fraction. The bias in this case is 2^4-1-1 or 7. Here is how the 8-bit representation looks pictorally:

s exp frac

Converting binary numbers into real numbers. Converting between real numbers and a binary representation is similar in many ways to converting between integer decimal and binary, although it is slightly more complicated. To convert from a binary representation to a real number, we can follow the formula defined above N = (-1)^s * 2^exp-bias * 1.frac. We can use the sign bit (leftmost bit) to determine the sign of the result. We can then figure out exp (which is an unsigned number) and subtract bias from it to determine the power of 2. Finally, we can use frac to determine the last factor in the formula: 1.frac. frac is a sequence of bits where each bit represents a different negative power of 2, which is similar to a fraction in decimal except that the base is 2 and not 10. The first and leftmost bit in the fraction is the 1/2 place (2^-1), the second bit is the 1/4 place (2^-2), the third is the 1/8 place (2^-3), and so on. We add up all the fractions from positions where the bit is 1 and then add 1 to this result (since it's 1.fraction -- the 1 is implicit).

This is much easier to understand by example. Let's assume we're using an 8-bit, floating point representation and our value is the following:

11001101

The sign in this case is 1 since the leftmost bit is 1. The exponent bits are 1001 or 9 as an unsigned int. The fraction bits are 101 so the fraction is (1/2 + 0/4 + 1/8) or 5/8. 1.fraction is 13/8. So we can then plug these values into our formula to get:

N = (-1)^s * 2^exp-bias * 1.fraction = (-1)¹ * 2^9-7 * (13/8) = -13/2 = -6.5

Converting real numbers into binary numbers. To convert from a floating point value to a binary representation is more difficult. It's probably best demonstrated by example. Assume we want to convert -6.5 to binary. We know the sign bit must be 1 since -6.5 is negative. We can then work with the unsigned value: 6.5. Since 6 is 110 in binary, we will need to move the decimal point over two spots to the left in order to normalize it. This means the power of 2 factor will need to be 2². In other words, 6 is greater than 2² but less than 2³ so the actual exponent will need to be 2. Since the bias is 7, this means that the exponent field must be 9, which is 1001 in binary. Finally, to find the fraction, we convert the whole part of the floating point value, if there is a whole part, to binary. So we would convert 6 to 110. We can drop the leftmost 1, since it's implicit. This gives us just 10 and leaves one more bit to represent the fractional part of the floating point value. We can then use the algorithm from class to find the binary digits to represent .5:

Set float to float minus whole part (e.g., 6.5 - 6 => .5)
Loop while float is not 1 and there are bits remaining in the fraction field
     Multiply float by 2
     If float is greater than or equal to 1
          The next bit in the fraction field (on the right) is 1
          Subtract 1 from the float
     Otherwise
          The next bit in the fraction field (on the right) is 0

Since the fractional part of the floating point value is .5, this will give us an additional 1 on the right of the fraction field, making it 101. Putting all the pieces together (sign=1, exponent=1001, fraction=101), we get 11001101.

The entire algorithm looks as follows:

If f is negative
     Set sign bit in binary result to 1
     Make f positive
Otherwise
     Set sign bit in binary result to 0

Set actualExp to 0
If f is greater than or equal to 1
     Set wholePart to int(f)
     Loop while wholePart is not zero
          Increment actualExp
          Divide wholePart by 2
Otherwise
     Loop while f is less than 1
          Decrement actualExp
          Multiply f by 2
Set encodedExp to actualExp plus 7
Convert encodedExp (unsigned integer) to binary using conversions from previous labs
 and set exponent bits in binary result to converted value

If f is greater than or equal to 2
     Convert int(f) to decimal using conversions from previous labs, chopping off
      leading 1 (since implicit) and any extra bits beyond 3, and set fraction bits
      to converted value
     Set f to f minus int(f) (remove whole part)
Otherwise
     Set f to f minus 1 (remove implicit 1)
While f does not equal 1 and number of fraction bits is less than 3
     Multiply f by 2
     If f is greater than or equal to 1
          Set next fraction bit to 1
          Set f to f minus 1
     Otherwise
          Set next fraction bit to 0
If number of fraction bits is less than 3
     Add 0's onto end of the fraction bits until length is 3

Setup

Create a lab03 directory within the ~/cs220 directory that you created in lab 1 for use in this lab. Change to the newly-created lab03 directory. Copy the provided files from the directory /classes/f08/cs220/labs/lab03 to your new lab03 directory.

If you have forgotten how to manipulate files and directories, check out the Using Linux tutorial or lab 2 from CS 124. As a reminder (these commands will not be provided in later labs), here are the commands you need to perform the steps above:

bash$ mkdir ~/cs220/lab03
bash$ cd ~/cs220/lab03
bash$ cp /classes/f08/cs220/labs/lab03/* ~/cs220/lab03/

Note: the rest of this lab assumes you are in your lab03 directory.

The file TextIO.java should now have been copied to your lab03 directory. This file defines some methods for reading data typed by the user into your program. Note: it must reside in the same directory as the programs that use it, so make sure it was actually copied to the lab03 directory. You will only need to use three methods from TextIO in this lab: getln(), getlnInt(), and getlnFloat() (don't forget the "ln" in either method, it's important). The first reads a String from the user, the second reads an int, and the third reads a float. See Section 2.4 of Professor Eck's Java Textbook for more details on TextIO.

Exercises

Here are the exercises for this week's lab writeup. The first two exercises are required and the third exercise is extra credit (i.e., it is optional). The solutions are due by the start of lab next Thursday. Remember to use good programming style as laid out in lab 1.

Write a Java program called HotelReserve.java for keeping track of the hotel room availability. The program will allow you to record the rooms that are available and those that are taken. For simplicity, rooms cannot be reserved in advance. Although this program is fairly simple, you are required to use a bit vector (and not an array or String) to keep track of the rooms that are available and those that are taken. The hotel has 32 rooms. You will use a single integer (which has 32 bits) to represent the status of the 32 rooms. If the corresponding bit is 0 (you can decide which bit corresponds to which room), then the room is free, otherwise the room is taken. You should manipulate the bit vector using the built-in Java operators: ~, &, |, ^, <<, >>> (in this case, you will probably not want to use >>). You may not use any external classes (including Strings) to manipulate the bit vector. The only external class you will need is TextIO for reading input from the user.

Here is a sample run of the program (user input is underlined):
```
Hotel room system 
Options: 
         0: exit 
         1: take a room 
         2: free a room 
         3: print status of rooms 
Enter an option: 1
Enter room (0-31): 3
Room 3 taken 

Hotel room system 
Options: 
         0: exit 
         1: take a room 
         2: free a room 
         3: print status of rooms 
Enter an option: 1
Enter room (0-31): 22
Room 22 taken 

Hotel room system 
Options: 
         0: exit 
         1: take a room 
         2: free a room 
         3: print status of rooms 
Enter an option: 3
Rooms taken: 3 22
Rooms available: 0 1 2 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 23 24 25 26 27 28 29 30 31 

Hotel room system 
Options: 
         0: exit 
         1: take a room 
         2: free a room 
         3: print status of rooms 
Enter an option: 2
Enter room (0-31): 3
Room 3 freed 

Hotel room system 
Options: 
         0: exit 
         1: take a room 
         2: free a room 
         3: print status of rooms 
Enter an option: 3
Rooms taken: 22
Rooms available: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 23 24 25 26 27 28 29 30 31 

Hotel room system 
Options: 
         0: exit 
         1: take a room 
         2: free a room 
         3: print status of rooms 
Enter an option: 0
```
You will need to do some error checking to ensure that the user enters a valid option and/or room number. If they enter an invalid option or room number, your program should reprompt them until they enter a valid one.
Write a program, ConvBinToFP.java, which converts 8-bit binary numbers into a floating point value. You should use the 8-bit floating point representation discussed above. You should also do some error checking to ensure that the user enters a legal 8-bit binary value.

In addition, answer the following questions about this representation and put your answers in a comment at the top of your program.
- What are the smallest and largest non-negative values that can be expressed with this floating point representation.
- Are there real values that can be represented using the single precision floating point representation from class (32 bits) that cannot be represented with this 8-bit floating point representation and vice versa?
For extra credit, write a program, ConvFPToBin.java, which converts floating point values into a binary representation, using the 8-bit representation and algorithm discussed above.

Handin

Verify that your lab03 folder contains all of the files you created or modified for this lab, then copy your entire lab03 folder to the handin directory ~mcorliss/handin/cs220/username (where username is replaced with your username). For example, if your working directory is ~/cs220/lab03/ then you could do the following:

cp -r ~/cs220/lab03 ~mcorliss/handin/cs220/username

where username is replaced with your particular username (e.g., mcorliss).