BitVectors

A bit vector is a specialized kind of array. Basically, a bit vector is meant to condense bit values into an array so that no space is wasted. The reason why we don’t just create a boolean array is because most compilers use a larger datatype, such as an integer, in place of boolean. They do this because  most computers can only send a fixed amount of bits at a time through memory and to the processor. Every x86 machine from the 386 upwards can only send data in packs of 32 bits.

To design a bit vector you need to use bit manipulation. A method you can use is to create an array of long integers, which are usually 32 bits long. Make surwwswe your compiler supports 32-bit integers. Tho you can easily modify the bit vector class to work on larger or smaller integer sizes. After you created a Bitvector class, you can add a constructor and a destructor (like you normally would) along with some data members. The bit vector resize algorithm is similar to the array resize algorithm but instead of resizing the array to a certain number of integers, you can perform a few calculations and resize the vector to the given number of bits.

The Access Operator deviates the bitvector from the array class. You cannot retrieve the value at an index and at the same time allow you to modify the item. The array access operator returned a reference to the item in the given cell, but we are playing around with individual bits and not actual datatypes, your not allowed to return a reference to a specific bit. So the access operator is limited to retrieving the value at a given index.

Setting a bit within the bit vector is slightly more tricky. Because there is no single way to set an individual bit within an integer, you need to rely on the binary math rules such as: and operator and use the or operator to set bits.