Bitsset

Bitsset is a data structure used to store a set of boolean flags in a compact, fixed-length sequence of bits. Each position in a bitsset corresponds to an element in a predefined universal set, and the bit value indicates membership or state. Because the size is fixed at creation, bitsets are memory-efficient for representing large universes of elements.

Internally, a bitsset is typically implemented as an array of machine words (such as 8, 16, 32, or 64 bits). Access to a given position is achieved by locating the word containing that bit and applying a bit mask. This enables fast bitwise operations and set-like manipulation. Common semantics include indexing, setting, clearing, and flipping bits, as well as queries for the number of set bits or whether any or all bits are set.

Common operations include: set(index) to turn a bit on, reset(index) to turn it off, test(index) to check a bit, and flip(index) to invert it. Higher-level operations include count(), any(), none(), and all(). Bitwise operations across two bitssets—and, or, xor, and not—facilitate composite state updates, while shifts can move bits within the structure.

Bitssets appear in various forms across programming languages. Fixed-size variants resemble C++’s bitset, while dynamic variants resemble Java’s BitSet or Python’s bitarray. In practice, bitssets are used for flag storage, bitmap indexes, bloom-filter-style sketches, graph algorithms, and fast membership tests where a compact, parallelizable representation of many booleans is advantageous.

See also: bit array, bit mask, bloom filter, bitwise operations.