A bit array is effective at exploiting bit-level parallelism in hardware to perform operations quickly.
If w does not divide the number of bits to be stored, some space is wasted due to internal fragmentation.
Assuming its size (or length) to be n bits, the array can be used to specify a subset of the domain (e.g. {0, 1, 2, ..., n−1}), where a 1-bit indicates the presence and a 0-bit the absence of a number in the set.
A finite binary relation may be represented by a bit array called a logical matrix.
Only n/w memory accesses are required: Both of these code samples exhibit ideal locality of reference, which will subsequently receive large performance boost from a data cache.
As with character strings it is straightforward to define length, substring, lexicographical compare, concatenation, reverse operations.
When this operation is not available on the processor, it's still possible to proceed by successive passes, in this example on 32 bits: The find first set or find first one operation identifies the index or position of the 1-bit with the smallest index in an array, and has widespread hardware support (for arrays not larger than a word) and efficient algorithms for its computation.
In particular: Because of their compactness, bit arrays have a number of applications in areas where space or efficiency is at a premium.
Bit arrays and the operations on them are also important for constructing succinct data structures, which use close to the minimum possible space.
Bit arrays are also a useful abstraction for examining streams of compressed data, which often contain elements that occupy portions of bytes or are not byte-aligned.
For example, the compressed Huffman coding representation of a single 8-bit character can be anywhere from 1 to 255 bits long.
In information retrieval, bit arrays are a good representation for the posting lists of very frequent terms.
The APL programming language fully supports bit arrays of arbitrary shape and size as a Boolean datatype distinct from integers.
Bits may be accessed individually via the usual indexing notation (A[3]) as well as through all of the usual primitive functions and operators where they are often operated on using a special case algorithm such as summing the bits via a table lookup of bytes.
In Java, the class BitSet creates a bit array that is then manipulated with functions named after bitwise operators familiar to C programmers.
[5] The class supports random access and bitwise operators, can be iterated over, and its Length property can be changed to grow or truncate it.
They can be manipulated using the usual bitwise operators (~ | & ^),[6] and individual bits can be tested and set using the vec function.
Common Lisp provides a one-dimensional bit-vector implementation as a special case of the built-in array, acting in a dual capacity as a class and a type specifier.
[11] In addition to the general functions applicable to all arrays, dedicated operations exist for bit vectors.