Bit Vector Set Implementation

Question

while reading a chapter on basic operations on sets from a book of data structures using aho, I came across the next line in the bitwise vector implementation of sets of sets ...

if the universal set is sufficiently small so that a bit vector fits in one computer word, then union, intersection and difference can be performed by single logical operations in the language of the underlying machine.. 

the bit-vector implementation of sets implies that a set is denoted by an array, whose indices denote the elements of the set, and the contents of the index are one if it is a member of the array and zero if not .... therefore, operations with elements, insertion and deletion can be performed during constant time ... but can anyone show me how intersection, union and difference can be performed by single logical operations, as indicated in the excerpt ... plz give an example (or code) for any of the three operations ....

Answer 1

Suppose you have a computer with a 32-bit word, and you want to represent sets over a domain with 32 elements. For example, subsets {0 ... 31}.

The sets are represented by a single integer in which the bit # x is 1 if and only if x is in the set. Thus, the set {0, 1, 17, 30} will be

 01000000000000100000000000000011 

We map bits from 31 to 0, from left to right, by convention.

With this view:

• Intersection is AND binary ( x & y )
• Union is a binary OR ( x | y )
• The set difference is binary AND NOT ( x & ~y )
• Symmetric Set Difference - Binary XOR ( x ^ y )

Answer 2

The indicated sets s1 and s2 ,

• Intersection s1 & s2
• Union s1 | s2 s1 | s2
• Difference s1 & ~s2