A bit array (also known as bitmask, 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 kw bits, where w is the number of bits in the unit of storage, such as a byte or word, and k is some nonnegative integer. If w does not divide the number of bits to be stored, some space is wasted due to internal fragmentation. Definition A bit array is a mapping from some domain (almost always a range of integers) to values in the set {0, 1}. The values can be interpreted as dark/light, absent/present, locked/unlocked, valid/invalid, et cetera. The point is that there are only two possible values, so they can be stored in one bit. As with other arrays, the access to a single bit can be managed by applying an index to the array. 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. This set data structure uses about n/w words of space, where w is the number of bits in each machine word. Whether the least significant bit (of the word) or the most significant bit indicates the smallest-index number is largely irrelevant, but the former tends to be preferred (on little-endian machines). Basic operations Although most machines are not able to address individual bits in memory, nor have instructions to manipulate single bits, each bit in a word can be singled out and manipulated using bitwise operations. In particular: OR to set a bit to one: 11101010 OR 00000100 = 11101110 AND to set a bit to zero: 11101010 AND 11111101 = 11101000 AND to determine if a bit is set, by zero-testing : 11101010 AND 00000001 = 00000000 = 0 11101010 AND 00000010 = 00000010 ≠ 0 XOR to invert or toggle a bit: 11101010 XOR 00000100 = 11101110 11101110 XOR 00000100 = 11101010 NOT to invert all bits. NOT 10110010 = 01001101 To obtain the bit mask needed for these operations, we can use a bit shift operator to shift