logo

UTK Notes


Lab 08: BITSET

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. There is a standard bitset data type, if you include bitset. However, you may not use it! You’re implementing this by hand.

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.



1
2
3
4



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
  1. 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:



1



Set 0 [31..0] : 0000_0000_0000_0000_0000_0000_0000_0000

After Set(39) call:



1
2



Set 0 [31..0] : 0000_0000_0000_0000_0000_0000_0000_0000
Set 1 [63..32]: 0000_0000_0000_0000_0000_0000_1000_0000
  1. 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):



1
2
3
4



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):



1



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.

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

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

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

You will use bitwise operators, hint: a form of Test, to test each digit and concatenate it to a string.

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.

Template

Copy the following template to help you get started with your code.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131



class BITSET {
    vector<int> mSets;
public:
    BITSET();
    bool Test(int index) const;
    void Set(int index);
    void Clear(int index);
    int GetNumSets() const;
    int GetSet(int index) const;
};
string ToBinary(int bit_set, int spacing=4);
int main() {
    BITSET sets;
    string command;
    int which;
    do {
        cout << "> ";
        if (!(cin >> command) || "q" == command) {
            // If cin fails for any reason, it usually means
            // an EOF state, break and quit.
            break;
        }
        // Handle the commands here
        if ("t" == command) {
            if (!(cin >> which)) {
                cout << "Invalid index\n";
            }
            else {
                cout << sets.Test(which) << '\n';
            }
        }
        else if ("s" == command) {
            if (!(cin >> which)) {
                cout << "Invalid index\n";
            }
            else {
                sets.Set(which);
            }
        }
        else if ("g" == command) {
            int spacing;
            string line;
            getline(cin, line);
            istringstream sin {line};
            if (!(sin >> which)) {
                cout << "Invalid index\n";
            }
            else {
                if (!(sin >> spacing)) {
                    spacing = 4;
                }
                cout << ToBinary(sets.GetSet(which), spacing) << '\n';
            }
        }
        else if ("c" == command) {
            // TODO: Finish the "clear" command here.
        }
        // TODO: Finish the rest of the commands here.
        else {
            cout << "Unknown command '" << command << "'\n";
        }
    } while (true);
    return 0;
}
// Write the function body for ToBinary:
string ToBinary(int bit_set, int spacing) {
    string ret;
    // TODO: Add values to the ret string. The constructor will
    // clear it to the empty string "".
    for (int i = 31;i >= 0;i--) {
        // TODO: Write the logical operation that tests the bit at index i
        if (/* ... */) {
            ret += '1';
        }
        else {
            ret += '0';
        }
        // TODO: Check to see if we need a space here.
        if (/* ... */) {
            ret += ' ';
        }
    }
    return ret;
}

// BITSET Class Members
BITSET::BITSET() :
   mSets(1, 0)
{}

bool BITSET::Test(int index) const {
    // Recall that each set has 32 bits
    int which_set = /* ... */ ; // TODO: FINISH THE ARITHMETIC HERE
    int which_bit = /* ... */ ; // TODO: FINISH THE ARTIHMETIC HERE
    if (which_set >= GetNumSets()) {
        // The BITSET is an "infinite" set, so if the requested set
        // is bigger than what we are storing, that means it's a 0.
        return false;
    }
    // TODO: Write the code to test the bit at which_set/which_bit
    // and return true if it's a 1 or false if it's a 0.
    return /* ... */;
}

void BITSET::Set(int index) {
    int which_set = /* ... */ ; // TODO: FINISH THE ARITHMETIC HERE
    int which_bit = /* ... */ ; // TODO: FINISH THE ARTIHMETIC HERE
    // TODO: You might need to expand the Set to accommodate the index
    // which_set. If you do not do this properly, you will get a runtime
    // error named 'out_of_range'
    // TODO: Finish the bitwise operator to set bit which_bit.
    mSets.at(which_set) = /* ... */;
}

void BITSET::Clear(int index) {
    int which_set = /* ... */ ; // TODO: FINISH THE ARITHMETIC HERE
    int which_bit = /* ... */ ; // TODO: FINISH THE ARTIHMETIC HERE
    if (which_set < GetNumSets()) {
        mSets.at(which_set) = /* ... */; // TODO: Finish the bitwise operation(s) to clear bit which_bit.
        // TODO: Write the code here to truncate empty sets--sets that are 0.
    }
}

int BITSET::GetNumSets() const {
    return static_cast<int>(mSets.size());
}

int BITSET::GetSet(int index) const {
    // TODO: Check to see if index exists!
    return mSets.at(index);
}

Our tests to grade your code will expect that the names of your methods are the same as given to you in the problem above. Do NOT change any fields or methods given to you directly.

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 [spacing] - 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. By default (if the user doesn't specify the optional spacing parameter), the spaces number will be 4. Since the TA is free to change this as he/she sees fit, 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.

Restrictions and Hints

  1. You must format and comment your code including a header, any TA or student who helped you, and inline-code comments.
  2. You must use logical, bitwise operators to test, set, and clear all binary digits (bits).
  3. 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.
  4. Think about the bitwise functions: Test, Set, and Clear. These will need to be used in this lab.

Compiling

You MUST build your program using the following command.



1



g++ -std=c++11 -Wall -o lab8 lab8.cpp

Plagiarism

Please remember that labs are an individual effort. Please review the plagiarism policy on the syllabus.

Submission

Submit your lab8.cpp file.