Bitset

A bitset is a data structure that compactly stores a sequence of bits, typically used to represent a set of boolean flags or membership in a fixed universe. Each bit position corresponds to an element, and the bit value indicates presence or state. Bitsets are usually implemented as an array of unsigned integers, with individual bits packed into the words for memory efficiency and fast bitwise operations.

Common operations include setting a bit to one, clearing a bit to zero, toggling a bit, and testing whether a bit is one. Many implementations also provide bulk operations such as and, or, xor, and not, as well as utilities to count the number of set bits, or to check if any or none of the bits are set. Some bitsets support finding the next set bit or iterating over all set bits, though iteration typically involves scanning the underlying words.

Bitsets can be fixed-size or dynamic. Fixed-size bitsets allocate space for a predefined number of bits, with size known at compile time in languages that specialize the type. Dynamic or runtime-size bitsets grow as needed when more bits are required; they may allocate additional memory and reconfigure internal storage.

Common language implementations include: C++ has std::bitset for fixed-size sets and Boost dynamic_bitset for runtime size; Java provides BitSet with expandable length; C# offers BitArray; Python has third-party libraries such as bitarray, while Python’s integers can be used as arbitrary-length bitsets.

Performance characteristics are favorable for bitwise operations, which run on machine words and are typically O(number of words) for bulk operations, with O(1) time for single-bit access. Bitsets are widely used for memory-efficient flags, bitmap indexes, sieve algorithms, and other applications requiring fast set operations on large universes. Limitations include handling dynamic resizing efficiently and potential iteration overhead when scanning for set bits.