CMSC 202 Spring 2001

Project 2

A Big Binary ADT

Assigned	05 March 2001
Due	18 March 2001

Background

Large scale projects generally consist of many objects, each of which brings an ADT to life. These classes use each other's services and may include other objects as their own private data members. One of the advantages of object oriented programming is the ability to design, develop and test each class independently of the others. Testing a class is accomplished by writing a test program that can be used to exercise the class by invoking each public method in various states.
In this project, you will develop a class according to the ADT specifications below. A test program has been written for you. Your job is to implement the class in such a way that it passes all the tests.

Description

On the Linux system at UMBC, integer variables are 32 bits in length. However, sometimes programs require values that exceed 32 bits in size. To fill this void you will implement a BigBinary class which emulates a 40-bit integer. (Yes, we know that our system supports a 64-bit "long long" variable type, and therefore BigBinary isn't' really needed if it's just 40-bits long, but we didn't want to deal with 65+ bit integers). Because the BigBinary represents integer values, it makes good sense to overload many arithmetic, logical and bit oriented operations so that we can use BigBinary objects just like the integers that they are designed to support.

The main driver for this project, Proj2.C is being provided for you. This program takes two integer values as command line arguments and exercises them as BigBinary objects. Your job is to implement the BigBinary class described below so that you can compile, link and run Proj2. You should run Proj2 using all combinations of values -- both positive, both negative, etc.

You will also be exposed to the "make" utility and "makefiles". A makefile is also provided for you for this project, and the TAs will discuss makefiles in discussion session this week. You are responsible for providing your own makefile for all future projects in this course.

Your Tasks:

Copy the file /afs/umbc.edu/users/d/e/dennis/pub/CMSC202/Proj2/Proj2.C into your directory.

Copy the file /afs/umbc.edu/users/d/e/dennis/pub/CMSC202/Proj2/Makefile into your directory.

Implement the BigBinary class as described below. Remember that your class definition should be in your .H file and the implementation in your .C file. NO CODE is to be written in the .H file.

Compile, link and test your BigBinary class until it successfully supports all required operations used in Proj2.C (and therefore produces the proper output)

Submit the required files

ADT Definitions

The BigBinary class must support the following public operations. You may create as many private data members or private member functions as you wish, but you may not provide any public operations other than those listed here. The specific parameters and return type of some operations are not specified and are up to you. Also, if there is a choice between implementing these operations as member or non-member (possibly friend) functions, that choice is also up to you. Just remember the two fundamental rules:

You MAY NOT provide any public operations other than those listed here
Your class must work with Proj2.C found in Mr. Frey's public directory

BigBinary (int N = 0) -- a constructor that creates a BigBinary object and initializes it to represent the value N. Note that N defaults to zero but may be positive, negative or zero.
parity ( ) -- the parity of a binary number is determined by the number of bits which are set (have a value of 1). The parity is "ODD" if an odd number of bits are set, and "EVEN" if an even number of bits are set. Returns 1 if the parity is ODD, 0 if the parity is EVEN
asHex ( ) -- returns a 'C' style string that is the hexadecimal representation of the value stored
operator+ -- adds two BigBinary objects and returns their sum
operator - -- binary operator minus that subtracts two BigBinary objects and returns their difference
setBit (int bit) -- sets the specified bit to 1 -- Note that bit 0 is the least significant bit (farthest to the right)
clearBit (int bit) -- sets the specified bit to 0 -- see note above
flipBit (int bit) -- changes the specified bit from 1 to 0 or vice versa -- see note above
operator<< -- outputs a BigBinary object as a string of 0s and 1s -- see sample output)
signBit ( ) -- returns 1 if the sign bit is set, 0 if not
operator< -- returns true if the left-hand BigBinary object is less than the right-hand BigBinary object, else returns false
operator> -- returns true if the left-hand BigBinary object is greater than the right-hand BigBinary object, else returns false
operator== -- returns true if the two BigBinary objects being compared are equal
operator!= -- returns true if the two BigBinary objects being compared are not equal
operator[ ] -- returns the value of the bit specified within the brackets
unary operator- -- unary operator minus that returns a BigBinary object that is the 2's complement negative value of the host BigBinary object
operator | -- returns the bit-wise arithmetic OR of two BigBinary objects
operator& -- returns the bit-wise arithmetic AND of two BigBinary objects
operator^ -- returns the bit-wise XOR (exclusive or) of two BigBinary objects

Implementation Requirements and Restrictions

Your implementation must use an array to represent the value stored in the BigBinary. Each element of the array represents a single bit.
To define the size of your array (and to make you code readable and maintainable), define a static const int in the private section of your class and initialize it to 40. This variable is the number of bits in your BigBinary class and can be used to define your array and anywhere in your methods that need it.
You must use " 2's complement" representation to store the value in your BigBinary class
Your BigBinary class must support positive, negative and zero values
All arithmetic operations must work properly for all combinations of positive, negative and zero values
Errors -- operations which refer to a single bit must guard against an invalid parameter. Since we have not studied proper technique for handling errors, your code should simply display an error to cerr and then do nothing. For example, setBit( int bit ) should check that the parameter, bit, is valid. If not, setBit should output an error and then return. Note that bits are numbered from the least significant bit (bit 0) to the most significant bit. This is the opposite of the way in which array indices are ordered.

Implementation Hints

Take an incremental approach to developing your class. That is, implement and test the operations one at a time. This means editing Proj2.C so that it only uses those operations you have implemented. You should feel free to do this, BUT...... the graders will be copying the original Proj2.C into your directory when they grade your project, so in the end, your class must work with the original Proj2.C, not your edited version.

You need a character array to hold the hexadecimal representation of your BigBinary

Some operations are similar (for example, operator== and operator!= ). Sometimes you can use operators you have already implemented when you write the code for a new operator. For example, suppose I had already written (and tested) operator==. Then operator!= may be written in as little as one line of code.

2's Complement

Almost all computers represent values as binary numbers using the 2's complement representation. In this representation, the high-order bit (bit [0] of your array) is the "sign" bit. If the bit is on, the value represented is negative. If the sign bit is off, the value is positive (or zero).
To change a positive value to negative, or a negative value to positive there are two steps

Complement all the bits (change all 0s to 1 and all 1s to 0, including the sign bit)
Add one

For example, let's change change +5 to -5:

Represent +5 in binary -- 00000101
Complement -- 11111010
Add one -- 11111011 to get -5

    We can validate this representation by adding this binary value with +5 to get 0.
              11111011    -5
         + 00000101   + 5
           --------   ---
           00000000     0

Similarly, we can change -5 back to +5 with same steps

-5 in binary -- 11111011
Complement-- 00000100
Add one-- 00000101 = 5

Hexadecimal

Because humans don't deal well with lots of 1s and 0s, computer scientists often use the hexadecimal (base 16) number system to represent values. In this system, there are 16 symbols -- 0 - 9, A, B, C, D , E, F where 0 - 9 have their usual meaning, A = 10, B = 11, and so forth.
Since 16 = 24, each group of 4 binary bits can be represented by one hex symbol. To change from binary to hex, group your binary digits in groups of 4 starting with the least significant bits and translate them into hex symbols based on the values listed above. For example, to change 01011100101 in to hex.

Break the bits into groups of four starting at the right --010 1110 0101. If the leftmost group has less than 4 digits, that's okay.

Now compute the value of each group:

010 = 2 1110 = 14 0101 = 5
Form the hexadecimal value: 2E5

Sample Output

    You can use this sample output to compare your results. Please note that this sample is not complete. Since Proj2 takes two numeric command line arguments, you should test every possible combination of positive, negative and zero values in every possible order.
    Also note that the graders may not use the same values used to generate this output.
    Your output does not have to be exact, but must be similar and easy to read.

Makefiles

The "make" utility is used to help control projects with large number of files. It consists of targets, rules, and dependencies.
For this project, simply typing the command make or make Proj2 at the Unix prompt will compile and link your source files with Proj2.C and produce a new executable called Proj2. Typing make clean will remove any extraneous files in your directory such as .o files, and core files. Typing make cleanest removes all .o files, core, Proj2 and backup files made by your editor. Copy the file /afs/umbc.edu/users/d/e/dennis/CMSC202/Proj2/Makefile to your directory.
See a documented makefile for more information, or see the Project page for a link to even more info about make

What to Submit

For this project, you must submit the following files:

Your makefile -- it must be named "makefile" or "Makefile". The graders will simply type "make" and your files must compile and link all source files as appropriate
BigBinary.H-- the definition file for the BigBinary class.
BigBinary.C -- the implementation file for the BigBinary class