while reading the chapter on basic operations on sets from the book of data structures by aho i came across the following line in the topic bit vector implementation 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..
a bit vector implementation of sets implies that a set is denoted by an array whose subscripts denote the elements of the set and the content of a subscript is one if it is the member of an array and zero if not....so member, insert and delete operations can be performed in a constant amount of time....but can anyone show me how intersection, union and difference can be performed by single logic operations as stated by the excerpt...plz give an example(or code) for any one of the three operations....
Lets 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 of {0...31}.
Sets are represented with a single integer in which bit# x is 1 if and only if x is in the set. So the set {0, 1, 17, 30} would be
01000000000000100000000000000011
We number bits from 31 to 0, left to right, by convention.
With this representation:
x & y
)x | y
)x & ~y
)x ^ y
)Given sets s1
and s2
,
s1 & s2
s1 | s2
s1 & ~s2
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With