887:, pseudo-objects found in structs with size equal to some number of bits, are in fact small bit arrays; they are limited in that they cannot span words. Although they give a convenient syntax, the bits are still accessed using bytewise operators on most machines, and they can only be defined statically (like C's static arrays, their sizes are fixed at compile-time). It is also a common idiom for C programmers to use words as small bit arrays and access bits of them using bit operators. A widely available header file included in the
25:
874:, etc.) pack the bits densely into whatever size the machine word is. Bits may be accessed individually via the usual indexing notation (A) 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.
197:
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
725:
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
562:
If we wish to find the number of 1 bits in a bit array, sometimes called the population count or
Hamming weight, there are efficient branch-free algorithms that can compute the number of bits in a word using a series of simple bit operations. We simply run such an algorithm on each word and keep a
654:
A bit array is the most dense storage for "random" bits, that is, where each bit is equally likely to be 0 or 1, and each one is independent. But most data are not random, so it may be possible to store it more compactly. For example, the data of a typical fax image is not random and can be
942:, creates a vector of bits fixed at a particular size 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. The
587:
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) | (x&0xaaaaaaaa) >> 1)).
735:
Because of their compactness, bit arrays have a number of applications in areas where space or efficiency is at a premium. Most commonly, they are used to represent a simple group of
Boolean flags or an ordered sequence of Boolean values.
659:
is commonly used to compress these long streams. However, most compressed data formats are not so easy to access randomly; also by compressing bit arrays too aggressively we run the risk of losing the benefits due to bit-level parallelism
1040:
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.
605:
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. When a
710:
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,
1086:
891:
system, xtrapbits.h, is “a portable way for systems to define bit field manipulation of arrays of bits.” A more explanatory description of aforementioned approach can be found in the
257:
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
222:. 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
986:
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
1212:. In addition to the general functions applicable to all arrays, dedicated operations exist for bit vectors. Single bits may be accessed and modified using the
466:
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
1202:
type exists, which explicitly excludes the dynamic characteristics. Bit vectors are represented as, and can be constructed in a more concise fashion by, the
1082:
918:
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
961:. As in C++, the operator does not return a reference, since individual bits are not directly addressable on most hardware, but instead returns a
1026:
structure, in its SML/NJ Library. It is not fixed in size and supports set operations and bit operations, including, unusually, shift operations.
823:
1011:(each element in the array usually represents 32 bits). The class supports random access and bitwise operators, can be iterated over, and its
1172:, bit vectors are used to sample values from the hardware models, and to represent data that is transferred to hardware during simulations.
1901:
583:). When this operation is not available on the processor, it's still possible to proceed by successive passes, in this example on 32 bits:
826:
of very frequent terms. If we compute the gaps between adjacent values in a list of strictly increasing integers and encode them using
1577:
1535:
789:
that can store large sets in a small space in exchange for a small probability of error. It is also possible to build probabilistic
206:−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
198:
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
1372:
695:
They allow small arrays of bits to be stored and manipulated in the register set for long periods of time with no memory accesses.
610:
is stored in a bit array, find first one can be used to identify the highest priority element in the queue. To expand a word-size
426:
496:
1 ≠ 0 word := word shift right 1 // do something with value index := index + 1 // if needed
978:
creates a bit array that is then manipulated with functions named after bitwise operators familiar to C programmers. Unlike the
870:
fully supports bit arrays of arbitrary shape and size as a
Boolean datatype distinct from integers. All major implementations (
1871:
702:, they often outperform many other data structures on practical data sets, even those that are more asymptotically efficient.
676:
Bit arrays, despite their simplicity, have a number of marked advantages over other data structures for the same problems:
575:
Vertical flipping of a one-bit-per-pixel image, or some FFT algorithms, requires flipping the bits of individual words (so
664:). Thus, instead of compressing bit arrays as streams of bits, we might compress them as streams of bytes or words (see
89:
1186:, acting in a dual capacity as a class and a type specifier. Being a derivative of the array, it relies on the general
988:
811:
data, which often contain elements that occupy portions of bytes or are not byte-aligned. For example, the compressed
61:
1810:
974:
108:
1600:
915:
871:
68:
1605:
1029:
46:
1570:
1679:
1940:
1048:, strings can be used as expandable bit arrays. They can be manipulated using the usual bitwise operators (
219:
174:
75:
1684:
1667:
1060:
969:
1162:, hardware busses and hardware signals in general. In hardware verification languages such as OpenVera,
1883:
1650:
1645:
867:
726:
huge space overhead and additional cache misses it causes, unless the machine only has word addressing.
42:
698:
Because of their ability to exploit bit-level parallelism, limit memory access, and maximally use the
57:
1640:
1512:
1458:
1440:
1320:
1163:
907:
524:
402:
186:
1494:
1324:
1674:
1633:
1563:
1476:
1033:
878:
246:
1914:
1891:
1159:
797:
406:
35:
1299:
503:, which will subsequently receive large performance boost from a data cache. If a cache line is
387:
1896:
1696:
1390:
1354:
954:
800:, which use close to the minimum possible space. In this context, operations like finding the
1822:
1777:
1739:
1239:
1229:
943:
819:
536:
500:
242:
238:
158:
1426:
1099:
of arbitrary length, which may be either fixed-length or varying. The array elements may be
1762:
1279:
390:
operator to shift the number 1 to the left by the appropriate number of places, as well as
146:
8:
1532:
1194:, which optionally permits the bit vector to be designated as dynamically resizable. The
656:
1805:
1790:
1655:
1615:
786:
665:
398:
154:
82:
1724:
1623:
1316:
804:
th 1 bit or counting the number of 1 bits up to a certain position become important.
661:
258:
815:
representation of a single 8-bit character can be anywhere from 1 to 255 bits long.
1747:
1340:
808:
759:
391:
383:
202:
bits, the array can be used to specify a subset of the domain (e.g. {0, 1, 2, ...,
1935:
1767:
1709:
1539:
1078:
993:
771:
230:
1859:
1837:
1662:
1586:
1022:
has no support for bit arrays, Standard ML of New Jersey has an extension, the
1000:
812:
740:
643:
607:
598:
564:
234:
1158:
natively support bit vectors as these are used to model storage elements like
397:
Given two bit arrays of the same size representing sets, we can compute their
1929:
1832:
1729:
1714:
1408:
1169:
1155:
923:
843:
185:
does not divide the number of bits to be stored, some space is wasted due to
1550:
1545:
1265:
1255:
1032:
likewise currently lacks standard support for bitwise operations, but both
827:
793:
based on bit arrays that accept either false positives or false negatives.
782:
752:
719:
550:
operations. The implementation of some of these operations is sensitive to
1336:
846:
where the parameter M is 1; this parameter is only normally selected when
796:
Bit arrays and the operations on them are also important for constructing
1827:
1752:
1234:
1175:
1019:
775:
1815:
1719:
1303:
1274:
790:
711:
706:
However, bit arrays are not the solution to everything. In particular:
699:
551:
223:
1220:
functions and an extensive number of logical operations is supported.
755:, and benefits strongly from a find-first-zero operation in hardware.
484:
0 to n/w-1 index := 0 // if needed word := a
161:
in hardware to perform operations quickly. A typical bit array stores
1757:
1260:
1250:
892:
883:
24:
1854:
1800:
1628:
1546:
1319:(December 1948) "Matrix development of the calculus of relations",
1244:
1110:
646:) can also be extended to a bit array in a straightforward manner.
614:
to longer arrays, one can find the first nonzero word and then run
245:
where the arithmetic is
Boolean, and such a composition represents
1555:
996:
internally as a bit vector, as a safer alternative to bit fields.
807:
Bit arrays are also a useful abstraction for examining streams of
751:
is in the queue; this data structure is used, for example, by the
1849:
1795:
1151:
1103:— each element begins on a byte or word boundary— or
1107:— elements immediately follow each other with no padding.
1844:
1785:
906:
s typically occupy the same space as a byte or an integer, the
770:
may be used. However, this term is frequently used to refer to
680:
They are extremely compact; no other data structures can store
1269:
899:
763:
1866:
1147:
1092:
1045:
858:, or roughly the term occurs in at least 38% of documents.
715:
170:
888:
150:
1198:, however, is not infinite in extent. A more restricted
1007:
collection class. It stores bits using an array of type
957:
provides bit arrays in its standard library, Phobos, in
922:
return a reference to an element, but instead returns a
169:
is the number of bits in the unit of storage, such as a
1052:), and individual bits can be tested and set using the
567:
article for examples of an efficient implementation.
1063:, you can access (but not set) a bit of an integer (
938:
is generally discouraged. Another unique STL class,
838:
is in the list. The implied probability of a gap of
1551:
vector<bool>: More
Problems, Better Solutions
926:. This might seem a minor point, but it means that
49:. Unsourced material may be challenged and removed.
1190:function to be configured with an element type of
934:a standard STL container, which is why the use of
563:running total. Counting zeros is similar. See the
1513:"CLHS: Function BIT-AND, BIT-ANDC1, BIT-ANDC2..."
1355:"dynamic_bitset<Block, Allocator> - 1.66.0"
1182:implementation as a special case of the built-in
1927:
1015:property can be changed to grow or truncate it.
830:, the result is a bit array with a 1 bit in the
822:, bit arrays are a good representation for the
671:
310:to determine if a bit is set, by zero-testing:
16:Array data structure that compactly stores bits
557:
1571:
1117:as native type. There are two SQL bit types:
872:Dyalog APL, APL2, APL Next, NARS2000, Gnu APL
766:, disk sectors, etc. In such cases, the term
758:Bit arrays can be used for the allocation of
337:0 (=0 ∴ bit isn't set) (≠0 ∴ bit is set)
1337:"SGI.com Tech Archive Resources now retired"
950:class whose size is specified at run-time.
233:may be represented by a bit array called a
1578:
1564:
518:
386:needed for these operations, we can use a
992:, which represents a Set of values of an
842:is 1/2. This is also the special case of
781:Another application of bit arrays is the
499:Both of these code samples exhibit ideal
157:. A bit array is effective at exploiting
109:Learn how and when to remove this message
1146:Hardware description languages such as
153:. It can be used to implement a simple
1928:
1300:"Linux Magic System Request Key Hacks"
1559:
618:on that word. The related operations
1347:
1292:
492:0 to w-1 value := word
47:adding citations to reliable sources
18:
1585:
1074:), as if it were an array of bits.
861:
252:
13:
1329:
14:
1952:
1526:
592:
241:, these arrays are composed with
527:it is straightforward to define
425:for difference), as well as the
181:is some nonnegative integer. If
23:
1505:
1487:
1469:
1451:
1441:"CLHS: System Class BIT-VECTOR"
916:partial template specialization
730:
443:n/w-1 complement_a :=
34:needs additional citations for
1459:"CLHS: Type SIMPLE-BIT-VECTOR"
1433:
1419:
1401:
1383:
1365:
1310:
1071:) using the bracket operator (
684:independent pieces of data in
649:
474:memory accesses are required:
218:is the number of bits in each
1:
1285:
1113:and PostgreSQL's SQL support
722:should be considered instead.
455:b difference := a
451:b intersection := a
447:a union := a
417:simple bit operations each (2
192:
672:Advantages and disadvantages
570:
7:
1902:Directed acyclic word graph
1668:Double-ended priority queue
1391:"perlop - perldoc.perl.org"
1373:".NET mscorlib source code"
1223:
1178:provides a one-dimensional
834:th position if and only if
558:Population / Hamming weight
379:NOT 10110010 = 01001101
343:to invert or toggle a bit:
10:
1957:
1495:"CLHS: Accessor BIT, SBIT"
666:Bitmap index (compression)
1910:
1882:
1776:
1738:
1695:
1614:
1593:
1321:Journal of Symbolic Logic
774:, which may use multiple
743:, where the bit at index
515:cache misses will occur.
1634:Retrieval Data Structure
1427:"8.10. Bit String Types"
1409:"vec - perldoc.perl.org"
1247:Chess and similar games.
868:APL programming language
798:succinct data structures
739:Bit arrays are used for
585:
407:set-theoretic difference
247:composition of relations
1915:List of data structures
1892:Binary decision diagram
1477:"CLHS: Section 2.4.8.4"
1143:is a positive integer.
519:More complex operations
1897:Directed acyclic graph
955:D programming language
902:, although individual
879:C programming language
747:is set if and only if
289:to set a bit to zero:
214:words of space, where
187:internal fragmentation
149:that compactly stores
1240:Binary numeral system
1230:Arithmetic logic unit
820:information retrieval
501:locality of reference
268:to set a bit to one:
243:matrix multiplication
239:calculus of relations
159:bit-level parallelism
1763:Unrolled linked list
1429:. 30 September 2021.
1377:github.com/microsoft
1280:Variable-length code
632:count trailing zeros
376:to invert all bits:
147:array data structure
43:improve this article
1941:Bit data structures
1811:Self-balancing tree
1095:supports arrays of
1036:and Hugs provide a
944:Boost C++ Libraries
657:Run-length encoding
636:count trailing ones
624:count leading zeros
1791:Binary search tree
1656:Double-ended queue
1538:2019-10-16 at the
1533:mathematical bases
1379:. 15 October 2021.
1268:of 2 elements, or
1087:CFMutableBitVector
936:vector<bool>
928:vector<bool>
912:vector<bool>
787:set data structure
785:, a probabilistic
628:count leading ones
507:words, only about
259:bitwise operations
155:set data structure
1923:
1922:
1725:Hashed array tree
1624:Associative array
1516:www.lispworks.com
1499:www.lispworks.com
1481:www.lispworks.com
1463:www.lispworks.com
1445:www.lispworks.com
1343:. 2 January 2018.
1317:Irving Copilowish
1200:simple-bit-vector
1081:library contains
982:in C++, the Java
525:character strings
261:. In particular:
119:
118:
111:
93:
1948:
1748:Association list
1580:
1573:
1566:
1557:
1556:
1542:by Pr. D.E.Knuth
1520:
1519:
1509:
1503:
1502:
1491:
1485:
1484:
1473:
1467:
1466:
1455:
1449:
1448:
1437:
1431:
1430:
1423:
1417:
1416:
1413:perldoc.perl.org
1405:
1399:
1398:
1395:perldoc.perl.org
1387:
1381:
1380:
1369:
1363:
1362:
1351:
1345:
1344:
1333:
1327:
1314:
1308:
1307:
1296:
1219:
1215:
1211:
1201:
1197:
1193:
1189:
1185:
1181:
1141:
1136:
1133:
1126:
1123:
1073:
1070:
1066:
1051:
1039:
1025:
1014:
1010:
1006:
991:
985:
981:
977:
964:
960:
949:
941:
937:
929:
913:
905:
862:Language support
857:
582:
578:
392:bitwise negation
375:
342:
329:0 = 0000000
321:0 AND 0000000
309:
288:
267:
253:Basic operations
114:
107:
103:
100:
94:
92:
51:
27:
19:
1956:
1955:
1951:
1950:
1949:
1947:
1946:
1945:
1926:
1925:
1924:
1919:
1906:
1878:
1772:
1768:XOR linked list
1734:
1710:Circular buffer
1691:
1610:
1589:
1587:Data structures
1584:
1540:Wayback Machine
1529:
1524:
1523:
1511:
1510:
1506:
1493:
1492:
1488:
1475:
1474:
1470:
1457:
1456:
1452:
1439:
1438:
1434:
1425:
1424:
1420:
1407:
1406:
1402:
1389:
1388:
1384:
1371:
1370:
1366:
1353:
1352:
1348:
1335:
1334:
1330:
1323:13(4): 193–203
1315:
1311:
1298:
1297:
1293:
1288:
1226:
1217:
1213:
1206:
1199:
1195:
1191:
1187:
1183:
1179:
1139:
1131:
1128:
1121:
1118:
1079:Core Foundation
1072:
1068:
1064:
1049:
1037:
1023:
1012:
1008:
1004:
994:enumerated type
987:
983:
979:
973:
962:
958:
947:
939:
935:
927:
924:proxy reference
911:
903:
893:comp.lang.c faq
864:
847:
741:priority queues
733:
674:
652:
620:find first zero
595:
590:
589:
580:
576:
573:
560:
537:lexicographical
521:
497:
464:
380:
373:
371:
366:10 = 11101
358:00 XOR 00000
350:10 11101
340:
338:
307:
305:
286:
284:
265:
255:
231:binary relation
195:
125:(also known as
115:
104:
98:
95:
52:
50:
40:
28:
17:
12:
11:
5:
1954:
1944:
1943:
1938:
1921:
1920:
1918:
1917:
1911:
1908:
1907:
1905:
1904:
1899:
1894:
1888:
1886:
1880:
1879:
1877:
1876:
1875:
1874:
1864:
1863:
1862:
1860:Hilbert R-tree
1857:
1852:
1842:
1841:
1840:
1838:Fibonacci heap
1835:
1830:
1820:
1819:
1818:
1813:
1808:
1806:Red–black tree
1803:
1798:
1788:
1782:
1780:
1774:
1773:
1771:
1770:
1765:
1760:
1755:
1750:
1744:
1742:
1736:
1735:
1733:
1732:
1727:
1722:
1717:
1712:
1707:
1701:
1699:
1693:
1692:
1690:
1689:
1688:
1687:
1682:
1672:
1671:
1670:
1663:Priority queue
1660:
1659:
1658:
1648:
1643:
1638:
1637:
1636:
1631:
1620:
1618:
1612:
1611:
1609:
1608:
1603:
1597:
1595:
1591:
1590:
1583:
1582:
1575:
1568:
1560:
1554:
1553:
1548:
1543:
1528:
1527:External links
1525:
1522:
1521:
1504:
1486:
1468:
1450:
1432:
1418:
1400:
1382:
1364:
1346:
1328:
1309:
1290:
1289:
1287:
1284:
1283:
1282:
1277:
1272:
1263:
1258:
1253:
1248:
1242:
1237:
1232:
1225:
1222:
1001:.NET Framework
948:dynamic_bitset
863:
860:
813:Huffman coding
776:bits per pixel
732:
729:
728:
727:
723:
704:
703:
696:
693:
673:
670:
651:
648:
644:find first set
616:find first one
612:find first one
608:priority queue
603:find first one
599:find first set
594:
593:Find first one
591:
586:
581:b0 ... b30 b31
577:b31 b30 ... b0
572:
569:
565:Hamming weight
559:
556:
520:
517:
476:
431:
394:if necessary.
382:To obtain the
378:
345:
312:
291:
270:
254:
251:
235:logical matrix
194:
191:
117:
116:
31:
29:
22:
15:
9:
6:
4:
3:
2:
1953:
1942:
1939:
1937:
1934:
1933:
1931:
1916:
1913:
1912:
1909:
1903:
1900:
1898:
1895:
1893:
1890:
1889:
1887:
1885:
1881:
1873:
1870:
1869:
1868:
1865:
1861:
1858:
1856:
1853:
1851:
1848:
1847:
1846:
1843:
1839:
1836:
1834:
1833:Binomial heap
1831:
1829:
1826:
1825:
1824:
1821:
1817:
1814:
1812:
1809:
1807:
1804:
1802:
1799:
1797:
1794:
1793:
1792:
1789:
1787:
1784:
1783:
1781:
1779:
1775:
1769:
1766:
1764:
1761:
1759:
1756:
1754:
1751:
1749:
1746:
1745:
1743:
1741:
1737:
1731:
1730:Sparse matrix
1728:
1726:
1723:
1721:
1718:
1716:
1715:Dynamic array
1713:
1711:
1708:
1706:
1703:
1702:
1700:
1698:
1694:
1686:
1683:
1681:
1678:
1677:
1676:
1673:
1669:
1666:
1665:
1664:
1661:
1657:
1654:
1653:
1652:
1649:
1647:
1644:
1642:
1639:
1635:
1632:
1630:
1627:
1626:
1625:
1622:
1621:
1619:
1617:
1613:
1607:
1604:
1602:
1599:
1598:
1596:
1592:
1588:
1581:
1576:
1574:
1569:
1567:
1562:
1561:
1558:
1552:
1549:
1547:
1544:
1541:
1537:
1534:
1531:
1530:
1517:
1514:
1508:
1500:
1496:
1490:
1482:
1478:
1472:
1464:
1460:
1454:
1446:
1442:
1436:
1428:
1422:
1414:
1410:
1404:
1396:
1392:
1386:
1378:
1374:
1368:
1360:
1359:www.boost.org
1356:
1350:
1342:
1338:
1332:
1326:
1322:
1318:
1313:
1305:
1301:
1295:
1291:
1281:
1278:
1276:
1273:
1271:
1267:
1264:
1262:
1259:
1257:
1254:
1252:
1249:
1246:
1243:
1241:
1238:
1236:
1233:
1231:
1228:
1227:
1221:
1210:
1205:
1177:
1173:
1171:
1170:SystemVerilog
1167:
1166:
1161:
1157:
1156:SystemVerilog
1153:
1149:
1144:
1142:
1134:
1124:
1116:
1112:
1108:
1106:
1102:
1098:
1094:
1090:
1088:
1084:
1080:
1075:
1062:
1057:
1055:
1047:
1042:
1035:
1031:
1027:
1021:
1016:
1002:
997:
995:
990:
976:
971:
966:
956:
951:
945:
933:
925:
921:
917:
909:
901:
896:
894:
890:
886:
885:
880:
875:
873:
869:
859:
855:
851:
845:
844:Golomb coding
841:
837:
833:
829:
825:
824:posting lists
821:
816:
814:
810:
805:
803:
799:
794:
792:
788:
784:
779:
777:
773:
772:raster images
769:
765:
761:
756:
754:
750:
746:
742:
737:
724:
721:
720:Bloom filters
717:
713:
709:
708:
707:
701:
697:
694:
691:
687:
683:
679:
678:
677:
669:
667:
663:
662:vectorization
658:
647:
645:
641:
637:
633:
629:
625:
621:
617:
613:
609:
604:
600:
584:
568:
566:
555:
553:
549:
545:
544:concatenation
541:
538:
534:
530:
526:
516:
514:
510:
506:
502:
495:
491:
487:
483:
479:
475:
473:
469:
462:
458:
454:
450:
446:
442:
438:
434:
430:
428:
424:
420:
416:
412:
408:
404:
400:
395:
393:
389:
385:
377:
369:
365:
361:
357:
353:
349:
344:
336:
332:
328:
324:
320:
316:
311:
303:
299:
295:
290:
282:
278:
274:
269:
262:
260:
250:
248:
244:
240:
236:
232:
227:
225:
224:little-endian
221:
217:
213:
209:
205:
201:
190:
188:
184:
180:
176:
172:
168:
164:
160:
156:
152:
148:
144:
140:
136:
132:
128:
124:
113:
110:
102:
99:December 2010
91:
88:
84:
81:
77:
74:
70:
67:
63:
60: –
59:
55:
54:Find sources:
48:
44:
38:
37:
32:This article
30:
26:
21:
20:
1704:
1685:Disjoint-set
1515:
1507:
1498:
1489:
1480:
1471:
1462:
1453:
1444:
1435:
1421:
1412:
1403:
1394:
1385:
1376:
1367:
1358:
1349:
1331:
1312:
1294:
1266:Finite field
1256:Bitmap index
1208:
1204:reader macro
1203:
1174:
1164:
1145:
1138:
1130:
1129:bit varying(
1120:
1114:
1109:
1104:
1100:
1096:
1091:
1089:structures.
1076:
1058:
1053:
1043:
1028:
1017:
998:
972:, the class
967:
959:std.bitmanip
952:
931:
919:
897:
882:
876:
865:
853:
852:) / log(1 −
849:
839:
835:
831:
828:unary coding
817:
806:
801:
795:
783:Bloom filter
780:
767:
760:memory pages
757:
753:Linux kernel
748:
744:
738:
734:
731:Applications
705:
689:
685:
681:
675:
655:compressed.
653:
639:
635:
631:
627:
623:
619:
615:
611:
602:
596:
574:
561:
547:
543:
539:
532:
528:
522:
512:
508:
504:
498:
493:
489:
485:
481:
477:
471:
467:
465:
460:
456:
452:
448:
444:
440:
436:
432:
422:
418:
414:
410:
403:intersection
396:
381:
372:
367:
363:
362:00 = 11101
359:
355:
354:10 XOR 00000
351:
347:
339:
334:
330:
326:
322:
318:
314:
306:
301:
300:1 = 111010
297:
296:0 AND 111111
293:
285:
280:
279:00 = 11101
276:
275:10 OR 00000
272:
263:
256:
228:
220:machine word
215:
211:
207:
203:
199:
196:
182:
178:
166:
165:bits, where
162:
142:
138:
134:
130:
126:
122:
120:
105:
96:
86:
79:
72:
65:
53:
41:Please help
36:verification
33:
1828:Binary heap
1753:Linked list
1235:Binary code
1176:Common Lisp
1115:bit strings
1097:bit strings
1083:CFBitVector
1050:~ | & ^
1020:Standard ML
1003:supplies a
791:hash tables
712:Judy arrays
650:Compression
429:of either:
226:machines).
58:"Bit array"
1930:Categories
1816:Splay tree
1720:Hash table
1601:Collection
1325:Jstor link
1304:Kernel.org
1286:References
1275:Judy array
1196:bit-vector
1188:make-array
1180:bit-vector
1160:flip-flops
1056:function.
946:provide a
884:bit fields
809:compressed
718:, or even
700:data cache
640:log base 2
552:endianness
427:complement
325:AND 000000
193:Definition
143:bit vector
139:bit string
69:newspapers
1872:Hash tree
1758:Skip list
1705:Bit array
1606:Container
1261:Bitstream
1251:Bit field
1105:unaligned
1038:Data.Bits
1018:Although
848:−log(2 −
571:Inversion
533:substring
388:bit shift
237:. In the
229:A finite
123:bit array
1801:AVL tree
1680:Multiset
1629:Multimap
1616:Abstract
1536:Archived
1245:Bitboard
1224:See also
1137:, where
1111:PL/pgSQL
1077:Apple's
1024:BitArray
1005:BitArray
579:becomes
523:As with
384:bit mask
333:= 000000
145:) is an
1855:R+ tree
1850:R* tree
1796:AA tree
1152:Verilog
1101:aligned
1030:Haskell
989:EnumSet
548:reverse
540:compare
313:1110101
135:bit set
131:bit map
127:bitmask
83:scholar
1936:Arrays
1884:Graphs
1845:R-tree
1786:B-tree
1740:Linked
1697:Arrays
1154:, and
1069:Bignum
1065:Fixnum
1013:Length
984:BitSet
980:bitset
975:BitSet
940:bitset
768:bitmap
764:inodes
692:words.
638:, and
529:length
409:using
405:, and
317:111010
292:111010
177:, and
85:
78:
71:
64:
56:
1778:Trees
1651:Queue
1646:Stack
1594:Types
1270:GF(2)
1184:array
914:is a
910:type
856:) ≤ 1
716:tries
642:(see
399:union
346:11101
271:11101
141:, or
90:JSTOR
76:books
1867:Trie
1823:Heap
1641:List
1218:sbit
1216:and
1209:bits
1168:and
1148:VHDL
1127:and
1119:bit(
1093:PL/I
1085:and
1061:Ruby
1046:Perl
999:The
970:Java
963:bool
953:The
904:bool
877:The
866:The
597:The
490:from
482:from
437:from
264:Use
175:word
171:byte
151:bits
62:news
1675:Set
1341:SGI
1214:bit
1192:bit
1067:or
1059:In
1054:vec
1044:In
1034:GHC
1009:int
968:In
932:not
930:is
920:not
908:STL
900:C++
898:In
889:X11
881:'s
818:In
668:).
601:or
494:and
486:for
478:for
463:b)
461:not
457:and
453:and
445:not
433:for
374:NOT
370:10
341:XOR
308:AND
287:AND
283:10
173:or
129:,
45:by
1932::
1497:.
1479:.
1461:.
1443:.
1411:.
1393:.
1375:.
1357:.
1339:.
1302:.
1207:#*
1150:,
965:.
895:.
778:.
762:,
714:,
634:,
630:,
626:,
622:,
554:.
546:,
542:,
535:,
531:,
513:wk
488:b
480:i
449:or
441:to
439:0
435:i
401:,
304:0
266:OR
249:.
189:.
163:kw
137:,
133:,
121:A
1579:e
1572:t
1565:v
1518:.
1501:.
1483:.
1465:.
1447:.
1415:.
1397:.
1361:.
1306:.
1165:e
1140:n
1135:)
1132:n
1125:)
1122:n
854:p
850:p
840:n
836:n
832:n
802:n
749:k
745:k
690:w
688:/
686:n
682:n
660:(
511:/
509:n
505:k
472:w
470:/
468:n
459:(
423:w
421:/
419:n
415:w
413:/
411:n
368:0
364:1
360:1
356:1
352:1
348:0
335:1
331:0
327:1
323:1
319:1
315:0
302:0
298:0
294:1
281:1
277:1
273:0
216:w
212:w
210:/
208:n
204:n
200:n
183:w
179:k
167:w
112:)
106:(
101:)
97:(
87:·
80:·
73:·
66:·
39:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
