Project 3: BitVector & Application

Implementing BitVector of undetermined size implementing new concepts of copy constructor and assignment operators as well as destructors to determine the prime numbers up to a maximum range.

Educational Objectives. After successfully completing this assignment, the student should be able to accomplish the following:

Implement a class from a class definition

Implement class BitVector

Implement global operators for a class

Implement global operators class BitVector

Correctly separate class definition and implementation using files

Create executables of class client programs using makefiles and the Make utility

Test a class using specs and an existing test platform

Create client applications to determine the Prime Numbers up to a maximum range

Operational Objectives: Implement the class BitVector

Deliverables: bitvector.cpp, makefile

bitvector.h specification this file(make sure the name is bitvector.h):bitvector (2) copy.txt Download bitvector (2) copy.txt

Sample Main Routine to test if all of your member functions are defined: main-3.cpp Download main-3.cpp

Background

See lecture notes Chapter 4. Classes Part 1, Chapter 5. Pointers, Chapter 6. Classes Part 2, and Chapter 8. BitVectors.

Bit Operators in C/C++

operation	symbol	type	C++ Code
and	&	binary	z = x & y;
or	|	binary	z = x | y;
xor	^	binary	z = x ^ y;
not	~	unary	z = ~y;
left shift	<<	binary	z = y << n;
right shift	>>	binary	z = y >> n ;

Implementing a Bit Vector:

Determine the size of the Bit Vector:

In this assignment you will be asked to create a class that stores and access single bits. Since you can only allocate words (32 bits) at a time you need to determine the number of words you need to allocate. This is done by dividing the number of bits you need by 32 (integer division) and also getting the modulo of 32 and if it is not zero add one to the number. So lets say you needed 270 bits. 270/8 is 8 with a remainder of 14 so I would need 8+1 or 9 words.

Determine the location of the bit.

You need two pieces of information. (1) is which word is located in and (2) which bit within that word. if we assume that left most bit is the zero bit then we can use the following heuristic:

(1) Divide the bit number you want to find by 32 (integer division). This will give you the index into the word where the bit is located.

(2) Modulo the bit number you want to find by 32 and subtract it from 31. This will give you the offset or the number of positions that you must shift the word to locate the bit.

Setting the Mask.

Once you know the word and the offset you need to set a MASK so that you can manipulate that bit. The easiest way to do this is to put a integer 1 (one) in a number and shift it left (31-offset). Lets say the offset was 3. 31 minus 3 is 28 so we would shift the number left 28 times.

Set a bit:

To set a bit, put a one in the appropriate location in the mask and do a Logical OR on the work where the bit is located.

Unset a bit:

To unset a bit requires that you turn the bit off without affecting the other bits. This is a little tricky and there are two ways to do it.

(1) Find the bit you want to unset, check to see if it is set and flip it. Otherwise leave it alone.

(2) Find the word where the bit is. Set a Mask to all 1s , Set another mask to a single 1 and shift the bit into the position you want to unset. Do a Logical AND with the two masks and perform a logical AND with the results on the word where the bit is located.

Flip a bit:

To flip a bit, put a one in the appropriate location in the mask and perform a Logical XOR. If the bit is a 1 it will become a zero and if it is a zero it will become a 1.

Functional Requirements:

Implement the bitvector.h as stated in this document exactly.

Test the functionality of all of the methods even if they are not used in determining if a vector was set or not.

Write your own driver and be sure to test all of your member functions to see if the work properly. For instance, the Flip() should reverse all the bits. I would print out a before and after.

Your constructors should turn all bits initially to off.

Test the Flip() method that reverses all the bits by performing the Flip() and print out the bitvector to ensure all were flipped. I would print out a before and after .

The default constructor should allocate enough words to store 256 bits.

void Set (const size_t index); - Passes in a constant integer zero or larger and turns that particular bit on. If the bit value is out of range then take no action.

void Set (); - Sets all bits to ones. You can do this by setting each word to a -1.

void Unset (const size_t index); - Unsets all bits to zeros.

void Flip (const size_t index); - Passes in a constant integer zero or larger and flips that particular bit. If the bit value is out of range then take no action.

void Flip (); - Reverse all of the bits.

bool Test (size_t index) const; - Check the bit passed in as a positive integer value. Return a True if the bit is set to one, otherwise return zero. If the value is out of range then return zero.

void Print (string S); - Print the status of each bit. You may elect to print only the bits turned on or whether a bit is turned on or off. Passes a string to print as a header.

explicit BitVector (size_t); - Creates a new BitVector object of size passed in.

BitVector (const BitVector&); - Creates a new BitVector object and copies the contents of the the BitVector object passed in as a parameter.

~BitVector (); - Destroy and deallocate the memory for the BitVector Object.

BitVector& operator = (const BitVector& a); - Copy (over write) the contents of one BitVector into another. They must be of the same size.

size_t Size () const; - Return the size in the number of bits that the object will hold.

void Unsetmultiple (const size_t index); - A value is passed to this function and the function unsets all bit locations that are multiples of that value. This is part of the Sieve algorithm.

Grading Rubric:

The program compiles. If the program does not compile no further grading can be accomplished. Programs that do not compile will receive a zero.

(10 {points) The bitvector or class is defined properly. If the class cannot be compiled with the driver program we cannot grade it.

(15 Points) The makefile produces a proper executable for linprog.

(25 Points) The program executes without exception and produces output and each of the methods work properly:

Set

Unset

Constructors

Flip

Destructor

Print

Size

Assignment method

Copy constructor

Test

(25 Points 5 Points each) The program specifications are followed.

Files submitted properly using the tar command.

Size of the bitvector properly calculated ,

Default values are used and basic error checking ( ensuring values passed in are valid). Example is that you are not allowed to set a negative bit value or set a bit that exceeds the size of the bitvector.

All parameters passed in must be passed by reference ( address/pointers)

Assignment operator properly written as well as the other functions.

(10 Points)The program is documented (commented)

(5 Points)Use constants when values are not to be changed

(5 Points)Use proper indentation

(5 Points)Use good naming standards