Overview

You will be designing a BITSET class. This allows me to store a large number of Boolean values (true/false). The purpose of this lab is to use bitwise operators to solve a problem.

Assignment

The following members must be in a class called BITSET:

1. A private vector of integers. This will be where the actual bitset data is stored. The user may specify any integer as a bit, and your class must handle them transparently. Notice that this is a vector of integers, so there are only 32 bits per set. So, if the user specifies 66 as the bit that they want to set, that would be bit 2 (third bit from the right) of the third set (set #2). To find the set, think about the bit that needs to be set. If the user specifies 32, thats bigger than the first set, which has indices 0 - 31. So, it must be the first bit of the second set. Think about 66. The first set stores 0 - 31, the second set stores 32-63, and the third set stores 64-95. Therefore, it would be bit--64...65...66--the third bit from the right in set #2 (third set). Just like arrays, set numbers and bit numbers are 0-based indexed.

2. A public 0-argument constructor for the BITSET class. This constructor will resize the private vector of integers to the exact size 1 (see vector.resize() function). ALL newly created sets must have the set equal to 0 (all bits cleared).

3. A public accessor function called Test. This function will return true or false given an integer location. This function will test the given location. If that bit is 1, return true, otherwise return false. Remember, the location can be any integer. So, your Test function must be able to look at multiple sets. For example, if I call Test(62) with the following sets, I will get true, which means that bit #62 is 1. Whereas, if I call Test(65) with the following sets, I will get false, which means that bit #65 is 0. If the set is not present, return 0. Since we are trying to represent an infinite number of bits using a resizable vector, any bit tested that is above what actually exists will be 0. For example, if the size of the vector is 4, then Test with any parameter > 127 will return 0, since set index 3 [the fourth set] will represent up to and including bit 127.

Set 0 [31..0] : 0000_0000_0000_0000_1100_0000_1110_1000 Set 1 [63..32] : 0110_0111_0000_0000_0000_0000_0000_0001 Set 2 [95..64] : 0000_0000_0000_0011_0000_0000_0110_0101 Set 3 [127..96]: 0000_0000_1111_1110_0000_0000_0000_0001

4. A public mutator function called Set. This function will return nothing and take an integer location. This function will set the given bit to 1. Notice that you originally set the number of sets to 1 in the constructor. Your Set() function must be able to "grow" the vector should it need to. For example, if I specify bit 39, that exceeds the first set, which stores bits 0-31. So, you need to grow the vector by adding an additional set. By default, all bits in a set will be 0. Bit 39 would be the 8th bit (bit #7) in the second set. If the given bit is already 1, this function has no effect.

Before Set(39) call:

Set 0 [31..0] : 0000_0000_0000_0000_0000_0000_0000_0000

After Set(39) call:

Set 0 [31..0] : 0000_0000_0000_0000_0000_0000_0000_0000 Set 1 [63..32]: 0000_0000_0000_0000_0000_0000_1000_0000

5. A public mutator function called Clear. This function will return nothing and take an integer location. This function is the opposite of Set() and will set the given bit to 0. If the Clear() function must also "shrink" the set vector if the upper sets have been cleared to 0. The following illustrates a scenario with the function call to Clear(98):

Before Clear(98):

Set 0 [31..0] : 0000_0000_0000_0000_1100_0000_1110_1000 Set 1 [63..32] : 0000_0000_0000_0000_0000_0000_0000_0000 Set 2 [95..64] : 0000_0000_0000_0000_0000_0000_0000_0000 Set 3 [127..96]: 0000_0000_0000_0000_0000_0000_0000_0100

After Clear(98):

Set 0 [31..0] : 0000_0000_0000_0000_1100_0000_1110_1000

Notice that the Clear() function pruned the vector by resizing it from a size of 4 to a size of 1. Think carefully on how to test that a set is 0. Efficiency will be graded for this function.

6. A public accessor function called GetNumSets(). This function will take no parameters and will return the number of sets as an integer.

7. A public accessor function called GetSet(). This function will take a set index as a parameter and will return the entire set as a single, 4-byte integer. If the provided set doesn't exist, return 0.

8. You will be writing a non-member function called ToBinary. This function returns a string and takes two integers, a value, and spacing. This function will return the binary representation of the integer "value" as a string. The spacing integer determines how many binary digits will be placed into the string before a space is added. For example:

ToBinary(122, 4) would return a string "0000 0000 0000 0000 0000 0000 0111 1010". Notice that spaces are added after FOUR (4) binary digits, since this was specified as the "spacing" parameter. Also, notice that even though there are 4 bits at the very end (0b1010), there is no additional space added. You must handle this special case! The spacing must be added starting from the most significant digit. If the user gives a number that is not a factor of 32, then you will have digits "left over". The "left over" digits must be the least significant digits.

Consider the bitset an infinitely large bitset. You are just dynamically manipulating the size using a vector to save memory. However, if a set does not exist in your vector, it can still be queried. Any non-existent set is automatically integer 0.

User Interface

The user interface for this lab is fairly straight forward. You will ask the user for a command. Some commands have parameters, and others do not. The command is a single character and can be as follows: t - Prints 1 or 0 depending on if the given bit # is 1 or 0. For example, "t 0" will test the very first bit and return 1 or 0.

s - Sets the given bit to 1. For example "s 1" will set bit index 1 (the second bit) to 1.

c - Clears the given bit to 0. For example, "c 2" will clear bit index 2 (the third bit) to 0.

g - Prints the binary representation of the given set. You must make sure the user cannot crash your program if they give you an invalid set. Remember to use your ToBinary() function for this. Otherwise, the spaces number will be 4, but make sure you still have this as a parameter, since the TA is free to change this as he sees fit! In other words, your ToBinary() function must operate correctly with any spaces parameter.

n - Prints the number of sets in the bitset. This will always be at least 1.

q - Quits and returns to the console

You must continually ask the user for one of these commands until they either send EOF (Control-D) or type 'q' for quit. Furthermore, all of these commands operate on the same BITSET class instance.

READ *** Restrictions and Hints

1. Warnings might be as bad as errors. The -Werror below will ensure that all warnings are considered errors. You may remove this switch until you test your code for submission. However, when you submit, there must be no warnings or errors!
2. You must format and comment your code, like you did in COSC102, including a header, any TA or student who helped you, and inline-code comments.
3. You must use logical, bitwise operators to test, set, and clear all binary digits (bits).
4. You are not putting one number per element in the vector. Since the vector is a vector of integers, that gives you 32 total 0s and 1s (bits). This means that the first 32 numbers are in set 0, the next 32 are in set 1, and so forth. I cannot stress this enough. We still get submissions of students putting a 1 or 0 in the vector: vector[index] = 0, vector[index] = 1. This is NOT what the lab intends for you to do.
5. Think about the bitwise functions: Test, Set, and Clear. These will need to be used in this lab.