Bit array

A bit array (also known as bit map, bit set, bit string, or bit vector) is an array data structure that compactly stores bits. It can be used to implement a simple set data structure. A bit array is effective at exploiting bit-level parallelism in hardware to perform operations quickly. A typical bit array stores ${\displaystyle kw}$ bits, where ${\displaystyle w}$ is the number of bits in the unit of storage, such as a byte or word, and ${\displaystyle k}$ is some positive integer. If ${\displaystyle w}$ does not divide the number of bits to be stored, some space is wasted due to internal fragmentation.