|
Data Structures and Algorithms
with Object-Oriented Design Patterns in C# |
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 
illustrates how this can be done.
The constant BITS is defined as the number
of bits in a single int.
Program: SetAsBitVector fields.
Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.