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