Lab 2: Two's Complement Binary and Bit Vectors

Introduction

Two's complement binary numbers. Unlike in the previous lab, in this lab you will work with negative, decimal numbers. You will use two's complement to encode binary numbers. In two's complement, the leftmost bit indicates the sign: 0 for non-negative and 1 for negative. For non-negative numbers, the encoding works the same as with unsigned numbers (see lab 1). The negation of a number is defined to be the ones complement (i.e., flipping each bit) plus one.

Here is how we map decimal numbers to a 3-bit, two's complement binary representation:

In two's complement, the max is 2^n-1-1 where n is the number of bits in the binary representation and the min is -2^n-1 (because of 0, there is one more positive than negative value). If we take the two's complement of any number (i.e., flip all the bits and add 1) we get the negation. For example, the two's complement of 011 (3 in decimal) is 101 (-3 in decimal). This also works in reverse: the two's complement of 101 (-3 in decimal) is 011 (3 in decimal). As we would expect the two's complement of 000 is 000 (in other words, the negative of 0 is 0). Perhaps, unexpected, the negation of 100 (-4) is 100 (-4). This is because the negation of -4 (4) cannot be represented in 3-bit two's complement binary.

Converting two's complement binary to/from decimal. Converting between two's complement binary and decimal works similarly to converting between unsigned integers represented in binary and decimal. The only difference is that when when we have a negative value in either representation, we negate it before converting it, and then take the negation again after converting it. Therefore, the conversion is performed using unsigned numbers.

Here is the algorithm for converting from two's complement binary to decimal:

If sign bit is set in binary number
     Set number to two's complement of the original number
     Mark that it was originally negative
Convert to decimal (using conversion from lab 1)
If binary number was originally negative
     Negate decimal result

Here is the algorithm for converting from decimal to two's complement binary:

If decimal number is negative
     Set number to negation of original number
     Mark that it was originally negative
Convert to binary (using conversion from lab 1)
If decimal number was originally negative
     Set binary result to two's complement of that binary number

Hexadecimal. Because binary numbers can be quite long, it is sometimes difficult for humans to work with them. Instead, it is often much easier to write binary values in hexadecimal (base 16). In hexadecimal (or more simply hex), the digits are 0-9 and A-F (A is 10, B is 11, C is 12, D is 13, E is 14, F is 15). The decimal value 75 is 0x4B in hexadecimal (note: we put "0x" in front of the number to signify that it's hexadecimal not decimal).

Converting between binary and hexadecimal is very easy, which is why computer scientists often use hexadecimal. Each digit in hexadecimal maps to 4 binary digits and vice versa. The table below shows how we convert between any hexadecimal digit and 4 binary digits:

We can also convert between hexadecimal and decimal. However, if we already have a way of converting between hexadecimal and binary, and binary and decimal, the easiest solution is to use these two pre-existing techniques to convert between hexadecimal and decimal.

Data types and operators. All computers have built-in support for several data types and operators. A data type specifies a type of some storage unit. An operator is a function that takes as input one or more data elements with particular data types and computes some result. These are similar to the data types and operators defined within a particular programming language such as Java. For example, 'int' and 'String' are data types in Java and '+' and '.' (for accessing elements of an object) are operators. However, unlike at the programming language level, the machine built-in data types and operators are generally very basic. For example, the integer data type and '+' operator ('+' with integers not strings) are usually built in to the machine, while 'String' and '.' must be simulated using other built-in data types and operators.

You are undoubtably familiar at least at a functional level with the integer data type and arithmetic operators ('+', '-', '*', '/'). In the next lab, we will explore how the hardware for arithmetic operations and other operators work in a computer. But in this lab, we will look at one other simple, built-in data type, which you are probably not familiar with, and several operators for manipulating that data type.

Bit vectors. One often useful data type is the bit vector or bitmap. It can be used in a similar fashion as a boolean array in Java. For example, the following bit vector indicates whether each room in a hotel is busy or available.

The rooms are numbered from 0 to 15. The rightmost bit indicates whether room 0 is busy or available. Since it is 1, this indicates that room 0 is busy. Room 1, on the other hand, is available since the next bit is 0. Of course, a bit vector could be used in many other ways, just as a boolean array can be used in lots of ways.

There are several operators defined on bit vectors (note: the examples below use a 4-bit binary system):

• Bitwise NOT ('~'): This unary operation computes the logical NOT of one bit vector. It produces a bit vector where each bit is the opposite of the corresponding bit in the operand. For example:

  ~ 1001 => 0110

• Bitwise OR ('|'): This binary operation computes the logical (inclusive) OR of two bit vectors. It produces a bit vector where each bit is 1 only if either of the corresponding bits is 1 in the operands. For example:

  1001 | 1100 => 1101

  Note: the bitwise OR operator is '|', which is different from the boolean operator '||'.
  
  
• Bitwise AND ('&'): This binary operation computes the logical AND of two bit vectors. It produces a bit vector where each bit is 1 only if both of the corresponding bits is 1 in the operands. For example:

  1001 & 1100 => 1000

  Note: the bitwise AND operator is '&', which is different from the boolean operator '&&'.
  
  
• XOR ('^'): This binary operation computes the logical exclusive OR of two bit vectors. It produces a bit vector where each bit is 1 only if exactly one of the corresponding bits is 1 (but not both) in the operands. For example:

  1001 ^ 1100 => 0101

• Logical shift left ('<<'): This binary operation shifts the left operand bit vector left by the amount stored in the right operand. Zeros are inserted onto the right of the resulting bit vector. Bits that are shifted left past the leftmost position are dropped from the resulting bit vector. For example:

  1001 << 0001 (i.e., 1) => 0010

• Logical shift right ('>>>'): This binary operation shifts the left operand bit vector right by the amount stored in the right operand. Zeros are inserted onto the left of the resulting bit vector. Bits that are shifted right past the zero position are dropped from the resulting bit vector. For example:

  1001 >>> 0001 (i.e., 1) => 0100

• Arithmetic shift right ('>>'): This operation works like the logical shift right except that it preserves the sign of the original lefthand operand. If the value was non-negative then it works just like the logical shift right and inserts 0's onto the left of the resulting bit vector. But if the value was negative then it inserts 1's onto the left of the resulting bit vector. Just as with the logical shift right, bits that are shifted right past the zero position are dropped from the resulting bit vector. For example:

  1001 >>> 0001 (i.e., 1) => 1100

In Java, we can use ints as bit vectors. A Java int is represented using 32 bits, so it can serve as a 32-wide bit vector. We can use the operators above to manipulate the bit vector. For example, the Java code below uses bitwise NOT ('~'), bitwise AND ('&'), and logical shift right:

y = ~ x;   // sets y to bitwise NOT of bit vector stored in x
z = x & w; // sets z to bitwise AND of bit vectors stored in x and w
v = x >> w; // sets v to the result of shifting bit vector in x right by amount in w

Java does not have support for printing an int as a bit vector, however, we could use the conversion we defined above to build a binary value (in a String) from the arithmetic int and print it out.

Setup

Create a lab02 directory within the ~/cs220 directory the you created in lab 1 for use in this lab. Change to the newly-created lab02 directory. Copy the provided files from the directory /classes/f08/cs220/labs/lab02 to your new lab02 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/lab02
bash$ cd ~/cs220/lab02
bash$ cp /classes/f08/cs220/labs/lab02/* ~/cs220/lab02/

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

The file TextIO.java should now have been copied to your lab02 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 lab02 directory. You will only need to use two methods from TextIO in this lab: getln() and getlnInt(). The first reads a String from the user and the second reads an int. 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 three exercises are required and the fourth 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.

Update: exercise 3 and the extra credit were moved to lab 3. You should not submit these for lab 2.

1. Write a Java program called Convert.java for converting between two's complement binary, decimal, and hexadecimal number systems. The program should repeatedly prompt the user for a type of conversion: 1 means convert from decimal to binary and hexadecimal, 2 means convert from binary to decimal and hexadecimal, and 3 means convert from hexadecimal to decimal and binary. Once the user makes their selection, then your program should perform the conversion and print out the results. If the user enters 0 at the prompt, then the program should exit.

   Here is a sample run of the program (user input is underlined):

   Program for converting 8-bit representations 
   Options: 
          0: to exit 
          1: to convert decimal to binary and hexadecimal 
          2: to convert binary to decimal and hexadecimal 
          3: to convert hexadecimal to decimal and binary 
   Select an option: 1
   Enter a decimal integer: 56
   Binary representation: 00111000 
   Hexadecimal representation: 0x38 
   
   Program for converting 8-bit representations 
   Options: 
          0: to exit 
          1: to convert decimal to binary and hexadecimal 
          2: to convert binary to decimal and hexadecimal 
          3: to convert hexadecimal to decimal and binary 
   Select an option: 2
   Enter a binary value: 00111000
   Decimal representation: 56 
   Hexadecimal representation: 0x38 
   
   Program for converting 8-bit representations 
   Options: 
          0: to exit 
          1: to convert decimal to binary and hexadecimal 
          2: to convert binary to decimal and hexadecimal 
          3: to convert hexadecimal to decimal and binary 
   Select an option: 3
   Enter a hexadecimal value: 0x38
   Decimal representation: 56 
   Binary representation: 00111000 
   
   Program for converting 8-bit representations 
   Options: 
          0: to exit 
          1: to convert decimal to binary and hexadecimal 
          2: to convert binary to decimal and hexadecimal 
          3: to convert hexadecimal to decimal and binary 
   Select an option: 0
   

   You will need to do some error checking to ensure that all entered values can be encoded in an 8-bit, two's complement binary representation. If the user enters 2000 for a decimal value (with option 1), then your program should give an error and continue attempting to read in a good decimal value (it's left to you to determine what are good values). If the user enters fewer than 8 bits or more than 8 bits (with option 2), then your program should also give an error and continue attempting to read in a binary value with exactly 8 bits. Finally, if the user enters in a hexadecimal value that is not proceeded by 0x and does not contain exactly 2 hexadecimal digits (0-9, A-F -- you can assume A-F are uppercase), then your program should give an error and continue attempting to read in a correct hexadecimal value.

   Note: You must perform the conversions without the aid of external classes or packages. Java has many features in its extensive library (e.g., within Integer class or math package) for converting to binary values or hexadecimal values. You may not use any of these. In fact, the only external classes (or packages), you will need, and the only external classes (or packages) you are allowed to use, are String and TextIO. All other code, must be written and submitted by you. Feel free to look at your lab 1 (or copy code from your lab 1) to help with some parts of the conversions.

2. Write a Java program called BitVectorTest.java that manipulates user-specified bit vectors. Your program should start by reading in two ints using TextIO. Your program should use the conversion code from exercise 2 to print these out as bit vectors, although it will need to be adjusted to handle 32 bits rather than 8 bits since a Java integer is represented with 32 bits. Your program should then perform the following operations, printing the result to the screen as both an int and a bit vector (using the modified conversion code from exercise 1):

   • Bitwise NOT of the first bit vector.
   • Bitwise NOT of the second bit vector.
   • Bitwise OR of the first and second bit vectors.
   • Bitwise AND of the first and second bit vectors.
   • Bitwise XOR of the first and second bit vectors.
   • Logical shift left of the first bit vector by the value in the second operand.
   • Logical shift right of the first bit vector by the value in the second operand.
   • Arithmetic shift right of the first bit vector by the value in the second operand.

   Test the program out using several different values (i.e., run the program several times), and verify that it worked correctly. Note: you may not use any auxiliary classes or packages besides String and TextIO, including built-in classes such as Integer.

   In addition, answer the following questions, putting your answers in a comment within your program. Use your program to test your answers to these questions.

   • Imagine that Java had support for only bitwise NOT and bitwise OR (and not bitwise AND and bitwise XOR). Could we use the bitwise NOT and OR operations to somehow simulate bitwise AND and bitwise XOR?
   • When you add any number by 0 or multiply any number by 1, you get back the original value. Such values are known as identity values (i.e., 0 is the identity value with addition and 1 is the identity value with multiplication). Is there an identity value for bitwise OR, bitwise AND, and bitwise XOR? If so, what is the identity value for each operation?
   • Shifting is also useful as an operation on numeric operands rather than just bit vectors. If we shift an integer x left by amount n, what is the resulting value in terms of x and n? Express your answer using arithmetic operations as opposed to shifts. What about shift right? Does it matter whether we use the logical or the arithmetic shift right?

3. 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.

4. Extra credit: For extra credit, augment your program from exercise 1, to support a floating point representation in addition to decimal, binary, and hexadecimal. You should dedicate 1 bit to the sign, 4 bits to the exponent, and 3 bits to the significand. The conversion formula is as follows:

   N = (-1)S * 1.fraction * 2exponent-7

   If the user enters the value as a decimal, binary, or hexadecimal, your program should use this formula to find the approximate real value and print this out to the screen along with the other converted values (if they enter decimal or hexadecimal, your program will first have to convert it to binary before determining the real value). Your program should also include another option, which allows the user to enter a real number and have that converted to decimal, binary, or hexadecimal (to find the decimal and hexadecimal values, your program will first have to figure out the binary representation).

   Note: the extra credit will take a significant amount of time so do not attempt the extra credit until you finish the rest of the lab.

Handin

Verify that your lab02 folder contains all of the files you created or modified for this lab, then copy your entire lab02 folder to the handin directory ~mcorliss/handin/cs220/username (where username is replaced with your username). To copy a whole directory instead of a single file or a collection of files, use

  cp -r sourcedir targetdir

where sourcedir is the directory you want to copy and targetdir is where it will be copied to. The "-r" means "recursive" and tells the system to copy the source directory, any files it contains, any subdirectories it contains, any files those subdirectories contain, any subdirectories the subdirectories contain, etc. In this case, the following command will work regardless of what directory you are currently in:

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

Of course, if you named your cs220 directory something other than "cs220", you'll need to substitute your directory's name as appropriate. You can use the ls command (or dir) to check that the directory ~mcorliss/handin/cs220/username contains a lab02 directory, and that the directory ~mcorliss/handin/cs220/username/lab02 contains copies of the files you wanted to hand in.

You can hand things in multiple times - the cp command will overwrite any existing file with the same name.

You can also delete things if you hand in something you didn't want to. Remove files using the command:

  rm filename

where filename is replaced by the name of the file you want to remove (e.g. ~mcorliss/handin/cs220/username/lab02/Convert.java to remove the file Convert.java from your handin directory). Note: including the full path here is important - if you are in your own lab02 directory and type rm Convert.java, you'll delete your copy of the Convert.java and will have to redo exercise #1 from scratch.

Another very important note: rm deletes things for real so be careful when you use it - a deleted file is gone for good. (If the file had been in existence for a while before you deleted it, you may be able to recover a version from a system backup. You will lose any changes made to the file since the last backup, however.)

You can delete a directory with the command

  rmdir dirname

Note that the directory must be empty of all files before it can be removed.

Finally, you can delete files and directories all together with

  rm -r dirname

As with cp, the "-r" means recursive and means that it will delete the directory, all files it contains, all subdirectories it contains, all files contained in the subdirectories, all subdirectories contained in the subdirectories, etc. Warning: rm -r is a very powerful command and should be used with extreme caution.