Bitsets

Use a bitset when your possible items are small integer IDs and membership needs only one bit per ID. It can pack many yes/no answers into one machine word.

Read a set as bits

Universe: IDs 0 through 7
Set:      {1, 3, 4}

ID:       7 6 5 4 3 2 1 0
Bit:      0 0 0 1 1 0 1 0

insert 2: 0 0 0 1 1 1 1 0
remove 3: 0 0 0 1 0 1 1 0

The invariant is direct: bit i is 1 exactly when item i belongs to the set. A bitset stores membership, not associated values or duplicate counts. It is also called a bitmap in many contexts.

Set union becomes bitwise OR. Intersection becomes AND. Symmetric difference becomes XOR. To remove the members of B from A, use A AND the complement of B, restricted to the chosen universe.

Trace a membership operation

With machine words of w bits, item i lives in word i divided by w, rounded down. Within that word, its mask is 1 shifted left by i modulo w.

To insert, OR that mask into the word. To test membership, AND with the mask and check for a nonzero result. To delete, AND with the mask's complement. No other bit changes.

A fixed universe of U possible IDs needs O(U / w) machine words, even if few items are present. Membership, insertion, and deletion take O(1) word operations when the word index is directly addressable. Whole-set union and intersection take O(ceil(U / w)) operations.

Enumerating members must inspect the relevant words and emit every result. A hash set instead stores roughly in proportion to the number of present items, but pays overhead per entry. An ordered set supports predecessor and sorted-range operations without reserving a bit for every possible ID.

Choose a bitset for dense bounded IDs, flags, or repeated set intersections. Choose a hash set for sparse, large, or non-integer keys. Mapping arbitrary keys to dense IDs can make bitsets possible, but that mapping has its own cost.

Predict and modify

1. Which word and bit store ID 65 with 64-bit words?
2. Is a plain bitset a good fit for three IDs near one trillion?
3. Add complement within the universe.

class BitSet:
    WORD_BITS = 64

    def __init__(self, universe):
        if universe < 0:
            raise ValueError("universe must be nonnegative")
        self.universe = universe
        self.words = [0] * ((universe + self.WORD_BITS - 1) // self.WORD_BITS)

    def location(self, item):
        if not 0 <= item < self.universe:
            raise IndexError("item outside universe")
        return item // self.WORD_BITS, 1 << (item % self.WORD_BITS)

    def add(self, item):
        index, mask = self.location(item)
        self.words[index] |= mask

    def contains(self, item):
        index, mask = self.location(item)
        return bool(self.words[index] & mask)

    def discard(self, item):
        index, mask = self.location(item)
        self.words[index] &= ~mask

    def intersection(self, other):
        if self.universe != other.universe:
            raise ValueError("universes must match")
        result = BitSet(self.universe)
        result.words = [left & right for left, right in zip(self.words, other.words)]
        return result


left = BitSet(130)
right = BitSet(130)
for item in [1, 3, 4, 64, 129]:
    left.add(item)
for item in [3, 64, 100]:
    right.add(item)
left.add(2)
left.discard(3)
left.discard(3)
assert left.contains(2) and not left.contains(3)
common = left.intersection(right)
assert [item for item in range(130) if common.contains(item)] == [64]
assert left.contains(129)

Return to the data structures guide.