Write functions for computing union, intersection, and set difference on arbitrarily long bit vectors used to represent set membership as described in Section 9.3. Assume that for each operation both vectors are of equal length.

Transcribed Image Text:

9.3 Bit Vectors for Representing Sets Determining whether a value is a member of a particular set is a special case of searching for keys in a sequence of records. Thus, any of the search methods discussed in this book can be used to check for set membership. However, we can also take advantage of the restricted circumstances imposed by this problem to develop another representation. In the case where the set elements fall within a limited key range, we can repre- sent the set using a bit array with a bit position allocated for each potential member. Those members actually in the set store a value of 1 in their corresponding bit; those members not in the set store a value of 0 in their corresponding bit. For example, consider the set of primes between 0 and 15. Figure 9.1 shows the corresponding bit table. To determine if a particular value is prime, we simply check the corre- sponding bit. This representation scheme is called a bit vector or a bitmap. The mark array used in several of the graph algorithms of Chapter 11 is an example of such a set representation. If the set fits within a single computer word, then set union, intersection, and difference can be performed by logical bitwise operations. The union of sets A and B is the bitwise OR function (whose symbol is | in Java). The intersection of sets A and B is the bitwise AND function (whose symbol is & in Java). For example, if we would like to compute the set of numbers between 0 and 15 that are both prime and odd numbers, we need only compute the expression 0011010100010100 & 0101010101010101.