Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

Basic Operations

Program gif defines the constructor for the SetAsBitVector class as well as the three basic operations--Insert, IsMember, and Withdraw. The constructor takes a single argument tex2html_wrap_inline66461, which specifies the universe and, consequently, the number of bits needed in the bit array. The constructor creates an array of ints of length tex2html_wrap_inline66569, where tex2html_wrap_inline66571 is the number of bits in an int, and sets the elements of the array to zero. The running time of the constructor is tex2html_wrap_inline66573.

   program27801
Program: SetAsBitVector class constructor, Insert, Withdraw, and IsMember methods.

To insert an item into the set, we need to change the appropriate bit in the array of bits to one. The tex2html_wrap_inline57621 bit of the bit array is bit tex2html_wrap_inline66577 of word tex2html_wrap_inline66579. Thus, the Insert method is implemented using a bitwise or operation to change the tex2html_wrap_inline57621 bit to one as shown in Program gif. Even though it is slightly more complicated than the corresponding operation for the SetAsArray class, the running time for this operation is still O(1). Since tex2html_wrap_inline66571 is a power of two, it is possible to replace the division and modulo operations, / and %, with shifts and masks like this:

vector[item >> shift] |= 1 << (item & mask);
for a suitable definition of the constants shift and mask. Depending on the compiler and machine architecture, doing so may improve the performance of the Insert operation by a constant factor. Of course, its asymptotic performance is still O(1).

To withdraw an item from the set, we need to clear the appropriate bit in the array of bits and to test if an item is a member of the set, we test the corresponding bit. The IsMember and Withdraw methods in Program gif show how this can be done. Like Insert, both these methods have constant worst-case running times.


next up previous contents index

Bruno Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.