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 kw bits, where w is the number of bits in the unit of storage, such as a byte or word, and k is some positive integer. If w does not divide the number of bits to be stored, some space is wasted due to internal fragmentation.

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 kw bits, where w is the number of bits in the unit of storage, such as a byte or word, and k is some positive integer. If w does not divide the number of bits to be stored, some space is wasted due to internal fragmentation. = 01001101 To obtain the bit mask needed for these operations, we can use a bit shift operator to shift the number 1 to the left by the appropriate number of places, as well as bitwise negation if necessary. Given two bit arrays of the same size representing sets, we can compute their union, intersection, and set-theoretic difference using \frac{n}{w} simple bit operations each ( \frac{2n}{w} for difference), as well as the complement of either: for i from 0 to n/w-1 complement_a[i] := not a[i] union[i] := a[i] or b[i] intersection[i] := a[i] and b[i] difference[i] := a[i] and (not b[i]) If we wish to iterate through the bits of a bit array, we can do this efficiently using a doubly nested loop that loops through each word, one at a time. Only \frac{n}{w} memory accesses are required: for i from 0 to n/w-1 index := 0 // if needed word := a[i] for b from 0 to w-1 value := word and 1 ≠ 0 word := word shift right 1 // do something with value index := index + 1 // if needed Both of these code samples exhibit ideal locality of reference, which will subsequently receive large performance boost from a data cache. If a cache line is k words, only about \frac{n}{wk} cache misses will occur. exchange two 16-bit halfwords exchange bytes by pairs (0xddccbbaa -> 0xccddaabb) ... swap bits by pairs swap bits (b31 b30 ... b1 b0 -> b30 b31 ... b0 b1) The last operation can be written ((x&0x55555555) > 1)). Given a big file of IPv4 addresses (more than 100 GB) — we need to count unique addresses. If we use generic map[string]bool — we will need more than 64 GB of RAM, so we use the bit map, in Go: package main import ( "bufio" "fmt" "math/bits" "os" ) // bitsetSize is the number of bytes needed for 2^32 bits (512 MiB) const bitsetSize = 1 > 3 // Divide by 8 bitIndex := ip & 7 // Bit position 0-7 bitset[byteIndex] |= 1 In C++, although individual bool s typically occupy the same space as a byte or an integer, the STL type std::vector is a partial template specialization in which bits are packed as a space efficiency optimization. Since bytes (and not bits) are the smallest addressable unit in C++, the [] operator does not return a reference to an element, but instead returns a proxy reference. This might seem a minor point, but it means that vector is not a standard STL container, which is why the use of vector is generally discouraged. Another unique STL class, std::bitset , creates a vector of bits fixed at a particular size N at compile-time, and in its interface and syntax more resembles the idiomatic use of words as bit sets by C programmers. It also has some additional power, such as the ability to efficiently count the number of bits that are set. Like , the size of bitset must be specified at compile time, and cannot be inferred by the compiler. The Boost C++ Libraries provides a boost::dynamic_bitset class whose size is specified at run-time. The D programming language provides bit arrays in its standard library, Phobos, in std.bitmanip . As in C++, the [] operator does not return a reference, since individual bits are not directly addressable on most hardware, but instead returns a bool . In Java, the class ( java.util.BitSet ) creates a bit array that is then manipulated with functions named after bitwise operators familiar to C programmers. Unlike the bitset in C++, the Java BitSet does not have a "size" state (it has an effectively infinite size, initialized with 0 bits); a bit can be set or tested at any index. In addition, there is a class ( java.util.EnumSet ), which represents a Set of values of an enumerated type internally as a bit vector, as a safer alternative to bit fields. The .NET Framework supplies a Systems.Collections.BitArray collection class. It stores bits using an array of type int (each element in the array usually represents 32 bits). The class supports random access and bitwise operators, can be iterated over, and its Length property can be changed to grow or truncate it. Although Standard ML has no support for bit arrays, Standard ML of New Jersey has an extension, the BitArray structure, in its SML/NJ Library. It is not fixed in size and supports set operations and bit operations, including, unusually, shift operations. Haskell likewise currently lacks standard support for bitwise operations, but both GHC and Hugs provide a Data.Bits module with assorted bitwise functions and operators, including shift and rotate operations and an "unboxed" array over Boolean values may be used to model a Bit array, although this lacks support from the former module. In Perl, strings can be used as expandable bit arrays. They can be manipulated using the usual bitwise operators ( ~ , | , & and ^ ), and individual bits can be tested and set using the vec function. In Ruby, one can access (but not set) a bit of an integer ( Fixnum or Bignum ) using the bracket operator ( [] ), as if it were an array of bits. Rust supports using native numeric types as fixed-width bit arrays using bitwise operations. Third party libraries like bitvec provide dedicated interfaces. There were historically types std::collections::BitSet and std::collections::BitVec , however these were deprecated in version 1.3.0 and later removed in 2015. Apple's Core Foundation library contains CFBitVector and CFMutableBitVector structures. PL/I supports arrays of bit strings of arbitrary length, which may be either fixed-length or varying. The array elements may be aligned— each element begins on a byte or word boundary— or unaligned— elements immediately follow each other with no padding. PL/pgSQL and PostgreSQL's SQL support bit strings as native type. There are two SQL bit types: bit( n ) and bit varying( n ) , where n is a positive integer. Hardware description languages such as VHDL, Verilog, and SystemVerilog natively support bit vectors as these are used to model storage elements like flip-flops, hardware busses and hardware signals in general. In hardware verification languages such as OpenVera, e and SystemVerilog, bit vectors are used to sample values from the hardware models, and to represent data that is transferred to hardware during simulations. Common Lisp provides multi-dimensional bit arrays. A one-dimensional bit-vector implementation is provided as a special case of the built-in array , acting in a dual capacity as a class and a type specifier. Bit arrays (and thus bit vectors) relies on the general make-array function to be configured with an element type of bit , which optionally permits a bit vector to be designated as dynamically resizable. The bit-vector , however, is not infinite in extent. A more restricted simple-bit-vector type exists, which explicitly excludes the dynamic characteristics. Bit vectors are represented as, and can be constructed in a more concise fashion by, the reader macro #* bits . In addition to the general functions applicable to all arrays, dedicated operations exist for bit arrays. Single bits may be accessed and modified using the bit and sbit functions and an extensive number of logical operations is supported. ==See also== Arithmetic logic unit Binary code Binary numeral system Bitboard Chess and similar games. Bit field Bit mask Bitmap index Bitstream Finite field of 2 elements, or GF(2) Judy array Variable-length code ==References== ==External links== mathematical bases by Pr. D.E.Knuth vector<bool> Is Nonconforming, and Forces Optimization Choice vector<bool>: More Problems, Better Solutions

Text derived from https://en.wikipedia.org/w/index.php?oldid=1367290989 under CC BY-SA 4.0; modifications have been made.