BitSets

A bitset is a data structure that stores a sequence of bits, where each bit represents the presence or absence of an element in a universe of fixed size. Bitsets provide compact storage and fast bit-level operations compared with byte-oriented alternatives.

Typically implemented as an array of machine words, the length equals the size of the universe divided by the word size. Some languages offer fixed-size bitsets with compile-time known length, while others provide dynamic bitsets that can grow or shrink.

Common operations include setting, resetting, and testing individual bits, as well as flipping their value. Bitwise operations apply to whole bitsets, such as AND, OR, XOR, and NOT, and shifts or rotates move bits within the set. Counting set bits (popcount) and predicates like any(), none(), and all() summarize the contents. The cost of operations grows with the number of words, typically proportional to the size of the bitset.

Bitsets are well suited for membership testing in a fixed universe, fast set operations, adjacency representations in graphs, and memory-efficient flags. They are also used in algorithms such as bitset-based dynamic programming, bitmap indices, and Bloom-filter-like structures (though Bloom filters use dedicated bit arrays, not necessarily bitset types).

Examples in programming languages: C++ provides std::bitset for fixed-size bitsets and std::vector<bool> for a dynamic specialization; Java offers BitSet, a dynamically resizable bit array; Python supports bitwise operations on integers or the bitarray module for explicit bitsets.