[prev] 40 [next]

Sets as Bit-strings (cont)

Restrict possible values that can be stored in the Set
  • typically restricted to 0..N-1, (where N%32 == 0)
  • represent each value by position in large array of bits
  • insertion means set a bit to 1 (bit|1)
  • deletion means set a bit to 0 (bit&0)
  • bit position for value i is easy to compute
Representation of bit-list in C: 

#define NWORDS ???
unsigned int bits[NWORDS];

For most common C implementations, gives us #bits = 32*NWORDS.

This gives us a set which can hold values in range 0..(#bits-1)