Editing Bit array (section)

== Advantages and disadvantages ==
Bit arrays, despite their simplicity, have a number of marked advantages over other data structures for the same problems:
* They are extremely compact; no other data structures can store ''n'' independent pieces of data in ''n''/''w'' words.
* They allow small arrays of bits to be stored and manipulated in the register set for long periods of time with no memory accesses.
* Because of their ability to exploit bit-level parallelism, limit memory access, and maximally use the [[data cache]], they often outperform many other data structures on practical data sets, even those that are more asymptotically efficient.
However, bit arrays are not the solution to everything. In particular:
* Without compression, they are wasteful set data structures for sparse sets (those with few elements compared to their range) in both time and space. For such applications, compressed bit arrays, [[Judy array]]s, [[trie]]s, or even [[Bloom filter]]s should be considered instead.
* Accessing individual elements can be expensive and difficult to express in some languages. If random access is more common than sequential and the array is relatively small, a byte array may be preferable on a machine with byte addressing. A word array, however, is probably not justified due to the huge space overhead and additional cache misses it causes, unless the machine only has word addressing.