Problem 6.1 Implementing a Bit Vector

Introduction

In this problem, you will implement a Bit Vector class, a space-efficient way to store and manipulate binary values. A bit vector is an array of bits, where each bit can be set (1) or cleared (0). Unlike an array of booleans, which may use an entire byte per element, a bit vector packs multiple bits into a single integer, minimizing space usage.

Objective

Implement a C++ class BitVector that dynamically allocates memory for storing bits efficiently.

Class Requirements

• The class should support dynamic allocation and be able to resize itself when needed.
• The bit vector should be stored in an array of unsigned int or uint32_t, where each element stores 32 bits.
• Provide member functions to:
  • Set a bit at a given index.
  • Clear a bit at a given index.
  • Toggle a bit at a given index.
  • Check if a bit is set.
  • Print the bit vector.
• Implement proper memory management (constructor, destructor, and resizing logic).

Implementation

Since each uint32_t contains 32 bits, individual bits can be accessed and modified using bitwise operations. To set a bit at index \( i \), use bitwise OR (\(|\)) with a shifted mask: \[ \text{vec} \left[ \frac{i}{32} \right] \mathrel{|}= \left(1 \ll (i \bmod 32) \right) \] To clear a bit, use bitwise AND (\(\&\)) with the negated mask: \[ \text{vec} \left[ \frac{i}{32} \right] \mathrel{\&}= \sim \left(1 \ll (i \bmod 32) \right) \] Similarly, clearing a bit can also be done using XOR (^), and checking whether a bit is set can be achieved using bitwise AND. Work out the exact expressions for these operations using the same indexing method.

The following code contains the class definition (to be implemented by you) and a main function for testing.