My task requirement to implement an 'Expand' function of a bit vector in the BitVector class is as follows (header and main files are provided): 1. Implement the method BitVector::Expand(size_t nb) so that it has the effect enlarging the number of bits to at least nb while keeping the state of each of the existing bits in the enlarged object. The necessary steps in this implementation are: a. Calculate newByteArraySize = the number of bytes required for nb bits b. Using a locally declared pointer, create a new byte array of size newByteArraySize c. Initialize the new byte array to be the same as the old one where they share indices and to be zero for the "new" bits d. Set byteArraySize_ to newByteArraySize e. Delete the old byteArray_ f. Point byteArray_ to the newly allocated byte array 2. Expand(nb) should do nothing if nb does not excede the number of bits already allocated. 3. In all cases a call to Expand() should not change the bit values for any existing bits and should initialize all new bits to 0

My implementation code so far: #include #include namespace fsu { bool operator!= (const BitVector& v1 , const BitVector& v2) { return !(v1 == v2); } bool operator== (const BitVector& v1 , const BitVector& v2) { if (v1.Size() != v2.Size()) return 0; for (size_t i = 0; i < v1.Size(); ++i) { if (v1.Test(i) && !v2.Test(i)) return 0; if (v2.Test(i) && !v2.Test(i)) return 0; } return 1; } std::ostream& operator << (std::ostream& os, const BitVector& bv) { for (size_t i = 0; i < bv.Size(); ++i) os << bv.Test(i); return os; } //---------------------------------- // BitVector //---------------------------------- // public methods void BitVector::Expand (size_t newsize) // increase number of bits, retaining current values { // syntactically correct, non-functional implementation unsigned char * newByteArray; size_t newByteArraySize; if (newsize > Size() ) { newByteArraySize = (newsize + 7)/8; newByteArray = new unsigned char [newByteArraySize]; // initialize new byte array same as old, share indices and set to 0 for // new bits for (size_t i = 0; i <= Size(); ++i) { newByteArray[i] = Test(i); } for (size_t i = 0; i > Size(); ++i) { Unset(i); newByteArray[i] = Test(i); } byteArraySize_ = newByteArraySize; delete [] byteArray_; byteArray_ = newByteArray; } else if (newsize <= Size()) { //return byteArray_ with unchanged size } else if (newsize == 0) { std::cerr << "** BitVector error: memory allocation failure -- terminating program. "; exit (EXIT_FAILURE); //return; } }

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

void BitVector::Unset (size_t index) // make bit = 0: AND with inverted mask { byteArray_[ByteNumber(index)] &= ~ Mask(index); } void BitVector::Flip () // change all bit values { for (size_t i = 0; i < byteArraySize_; ++i) byteArray_[i] ^= 0xFF; } void BitVector::Flip (size_t index) // change bit value: XOR with mask { byteArray_[ByteNumber(index)] ^= Mask(index); } bool BitVector::Test (size_t index) const // return bit value { return 0 != (byteArray_[ByteNumber(index)] & Mask(index)); } // private methods size_t BitVector::ByteNumber (size_t index) const { // return index / 8 // shift right 3 is equivalent to, and faster than, dividing by 8 index = index >> 3; if (index >= byteArraySize_) { std::cerr << "** BitVector error: index out of range "; exit (EXIT_FAILURE); } return index; } unsigned char BitVector::Mask (size_t index) { // return mask for index % 8 // the low order 3 bits is the remainder when dividing by 8 size_t shiftamount = index & (size_t)0x07; // low order 3 bits return (unsigned char)0x01 << shiftamount; } } // namespace fsu #endif

Edit & Run

BitVect.h:

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

#ifndef _BITVECT_H #define _BITVECT_H #include namespace fsu { //---------------------------------- // BitVector //---------------------------------- class BitVector; std::ostream& operator << (std::ostream&, const BitVector&); class BitVector { public: explicit BitVector (size_t size); // construct a BitVector with spec\ ified size BitVector (const BitVector&); // copy constructor ~BitVector (); // destructor BitVector& operator = (const BitVector& a); // assignment operator size_t Size () const; // return size of bitvector void Set (); // make all bits = 1 void Set (size_t index); // make bit = 1 void Unset (); // make all bits = 0 void Unset (size_t index); // make bit = 0 void Flip (); // change all bits void Flip (size_t index); // change bit bool Test (size_t index) const; // return bit value private: // data unsigned char * byteArray_; size_t byteArraySize_; // methods size_t ByteNumber (size_t index) const; static unsigned char Mask (size_t index); } ; // class BitVector } // namespace fsu #endif