Bitsets library: uses bitmasks to represent finite sets of (small) natural numbers.

In this library, sets of natural numbers are represented as natural numbers
by saying

This representation enjoys certain efficiencies. In particular, operations like union, intersection, difference, and subset testing can be carried out in a "word at a time" fashion with bit operations.

But bitsets are only appropriate for sets whose elements are reasonably small numbers since the space needed to represent a bitset is determined by its maximal element. If your sets contain extremely small numbers---less than 28-60, depending on the Lisp---then they can be represented as fixnums and the bitset operations will be remarkably efficient.

Beyond this, bignums are necessary. Even though bignum operations generally involve memory allocation and are much slower than fixnum operations, using bignums to represent sets can still be very efficient. For instance, on 64-bit CCL, bignums are represented as a header/data pair where the data is an array of 32-bit words; operations like logand can smash together the two data arrays a word at a time.

Let's define the *density* of a set as its cardinality divided by its
maximal element plus one (to account for zero-indexing). Under this
definition, the set {1, 2, 4} has a density of 60%, whereas {96, 97, 98} has a
density of 3%.

Without destructive updates, you probably can't do much better than bitsets for dense sets. But bitsets are not good at representing sparse sets. For instance, you would need 8 KB of memory just to represent the singleton set {65536}.

The sparse bitsets library is an
alternative to bitsets that uses lists of

Convention:

a, b, ... denote set elementsX, Y, ... denote sets.

There is no such explicit

See reasoning for some notes about how to prove theorems about bitset functions.

(bitset-singleton a) - Constructs the set
{a} - Execution:
(ash 1 a) (bitset-insert a X) - Constructs the set
X U {a} - Execution:
(logior (ash 1 a) x) (bitset-list a b ...) - Constructs the set
{a, b, ...} - Execution: repeated
bitset-insert s (bitset-list* a b ... X) - Constructs the set
X U {a, b, ...} - Execution: repeated
bitset-insert s (bitset-delete a X) - Constructs the set
X - {a} - Execution:
(logandc1 (ash 1 a) x) (bitset-union X Y ...) - Constructs the set
X U Y U ... - Execution:
(logior x (logior y ...)) (bitset-intersect X Y ...) - Constructs the set
X \intersect Y \intersect ... - Execution:
(logand x (logand y ...)) (bitset-difference X Y) - Constructs the set
X - Y - Execution:
(logandc1 y x)

(bitset-memberp a X) - Determine whether
a is a member of the setX - Execution:
(logbitp a x) (bitset-intersectp X Y) - Determines whether
X andY have any common members - Execution:
(logtest x y) (bitset-subsetp X Y) - Determines whether
X is a subset ofY - Execution:
(= 0 (logandc2 y x)) (bitset-cardinality X) - Determines the cardinality of
X - Execution:
(logcount x)

(bitset-members X) - Constructs an ordinary ordered set with the elements of X.
- Expensive: must cons together all of the set elements.
- Important in reasoning about bitsets.

- Bitset-members
`(bitset-members x)`converts a bitset into an ordinary, ordered set.- Bitset-insert
`(bitset-insert a x)`constructs the setX U {a} .- Bitset-delete
`(bitset-delete a x)`constructs the setX - {a} .- Bitset-intersectp
`(bitset-intersectp x y)`efficiently determines ifX andY have any common members.- Bitset-intersect
(bitset-intersect X Y ...) constructs the setX \intersect Y \intersect ... .- Bitset-difference
`(bitset-difference x y)`constructs the setX - Y .- Bitset-subsetp
`(bitset-subsetp x y)`efficiently determines ifX is a subset ofY .- Bitset-union
(bitset-union X Y ...) constructs the setX U Y U ... .- Bitset-memberp
`(bitset-memberp a x)`tests whethera is a member of the setX .- Bitset-singleton
`(bitset-singleton a)`constructs the singleton set{a} .- Bitset-list
- Macro to construct a bitset from particular members.
- Bitset-cardinality
`(bitset-cardinality x)`determines the cardinality of the setX .- Bitset-list*
- Macro to repeatedly insert into a bitset.
- Utilities
- Utility functions.