Bitssets

Bitssets are a data structure designed to represent a set of bits, where each position in a universe corresponds to a possible element and the value at that position indicates membership. They can be fixed-width, with a complete array of bits, or dynamic, growing as elements are added.

Common implementations store bits in arrays of machine words and rely on fast bitwise operations. Languages and libraries provide built-in or standard implementations, such as dense bit vectors and dynamic bit sets, which enable compact storage and rapid membership, union, and intersection tests.

Basic operations include setting and clearing a bit, testing membership, and counting the number of set bits. Logical operations combine entire bitsets (AND, OR, XOR, NOT). Some variants support advanced queries like finding the index of the next set bit or rank and select.

Variants range from dense bitsets, which allocate a bit for every element, to sparse or compressed forms that store only active positions. Compressed representations, such as run-length or bitmap compression schemes, trade some speed for substantial memory savings on sparse data.

Applications appear in databases for bitmap indices, search engines for fast filtering, graph algorithms, and systems that manage permissions or feature flags. Bitsets enable fast, parallelizable operations and compact storage when the universe size is known in advance.