Bit Vector Representations

Subsets of a finite set can be efficiently represented as bit vectors, in which a given bit position is a 1 if the corresponding item is an element of the subset. Representing a 128-element set takes only 4 32-bit words of memory.

Operations on sets can be done by boolean instructions operating on whole words.

Set operation: Bit vector operation:
&isin &and with vector for element
or test bit
&cap &and
&cup &or
set complement of A ¬ A
set difference, A - B A &and ¬ B

Operations on the bit vector representation are O(n/32) , compared to O(n · m) with other methods.

Example use: assign a bit in a bit vector for each program variable or subexpression.

Contents    Page-10    Prev    Next    Page+10    Index