A bit vector is simply an array of bits (0s and 1s). A bit vector of length \(m\) takes much less space than an array of \(m\) pointers. Describe how to use a bit vector to represent a dynamic set of distinct elements with no satellite data. Dictionary operations should run in \(O(1)\) time.

Suppose we have some totally arbitrary set of distinct integers, such as 〈 8, 6, 7, 5, 3, 0, 9 〉. We can use a bit vector to represent this set of integers by having the bit position represent the integer value by holding a 1 if it is present and a 0 if it isn’t. So a bit vector representation of Jenny’s number would be:

Dictionary operations on a bit vector such as the one above are as follows:

BIT-VECTOR-SEARCH(V, k)

1 if V[k]:

2      return k

3 else return NIL

BIT-VECTOR-INSERT(V, x)

1 V[x] = 1

BIT-VECTOR-DELETE(V, x)

1 V[x] = 0

Each of these operations runs in constant time.