[Someone asked how to implement sets using arrays of bits. This is an excerpt from the additional explanation I posted.]

Newsgroups: comp.lang.c
From: scs@eskimo.com (Steve Summit)
Subject: Re: pascal-like set implementation
Message-ID: <E97GrL.F33@eskimo.com>
Date: Fri, 25 Apr 1997 18:02:08 GMT

If the repertoire of elements which might be contained in the set (what was that buzzword from set theory? ``Universe''?) is known, then the thing to do is set up a correspondence between those elements and the 0-based integers. (That is, if the universe is the elements ``apple'', ``pear'', and ``orange'', set apple = 0, pear = 1, and orange = 2. Hmm, you might be able to slickly use an enum for this.) Then, each set you want to manipulate is an array of BITNSLOTS(n) elements. To add an element to a set, turn on the corresponding bit. To remove an element from a set, turn off the corresponding bit. To compute the union of two sets, run the loop

	for(i = 0; i < BITNSLOTS(nb); i++)
		set3[i] = set1[i] | set2[i];

Computing the intersection is left as an exercise for the reader.

Printing a set out will obviously require iterating over all the bits, using BITTEST() to discover whether each bit is turned on, and then somehow going from the bit index back to the name of the element, if necessary. (We had a thread a week or two ago about how to print enum values symbolically. Here, since the indices are known to be 0-based integers, a simple lookup table, in the form of an array of strings, would suffice.)