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

Bit-Vector Sets

The common language runtime uses one byte of memory to store a single C# bool value. Furthermore, each bool in an array of bools occupies two bytes of memory[3]. However, since there are only the two values true and false, a single bit is sufficient to hold a bool value. Therefore, we can realize a significant reduction in the memory space required to represent a set if we use an array of bits. Furthermore, by using bitwise operations to implement the basic set operations such as union and intersection, we can achieve a commensurate reduction in execution time. Unfortunately, these improvements are not free--the operations Insert, IsMember, and Withdraw, all slow down by a constant factor.

Since C# does not directly support arrays of bits, we will simulate an array of bits using an array of ints. Program gif illustrates how this can be done. The constant BITS is defined as the number of bits in a single int.

Program: SetAsBitVector fields.

next up previous contents index

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