查看“︁位数组”︁的源代码

{{Multiple issues|
{{Refimprove|time=2020-06-25T07:41:29+00:00}}
{{Rough translation|time=2020-07-20T01:54:39+00:00}}
}}
{{NoteTA|G1=IT}}
'''位数组'''（{{lang-en|bit array}}），是一种能够紧凑地存储[[位]]的[[数组]]。位数组可以被用来实现简单的[[有限集合]]。它能够通过[[硬件]]中位级别的[[并行运算]]快速操作。通常情况下，一个位数组可以存储<math>kw</math>位信息（w是硬件中单个存储单元的位数，如[[字节]]或[[字 (计算机)|字]]，而k是一非负整数），如果w不能被计算机中存储单位的字节数整除，就会由于[[内存碎片化]]浪费一些内存空间。

== 定义 ==
位数组可以看作某个集合到<math>\{0, 1\}</math>的[[映射]]。其中的每个值可以解释做灯泡的明暗，元素的有无等等。因为每一个值只有两种可能性，所以能够把每个值存储进一位的内存。与其他种类的数组对应地，可以通过对数组应用索引的方式操作单个比特。假设某个位数组的大小是<math>n</math>位，那么这个数组就可以用来表示一个包含<math>n</math>个元素的集合（比如<math>[0, n) \cap N</math>）的子集，在每个位置上用<math>1</math>表示对应元素存在，<math>0</math>表示其不存在。这种数据结构占用<math>O\left(\dfrac{n}{w}\right)</math>的空间（<math>w</math>表示计算机里一个字的位数）。使用[[最高位]]还是[[最低位]]代表最小索引不会造成什么影响，但通常在[[字节序|小端序]]的机器上的实现偏向前者。

== 基本操作 ==
尽管大多数的机器不能在内存中定位单个的位，也没有操作单个位的指令，字里的每一位仍然可以用[[位运算]]分离并单独操作。比如：
* [[按位或]]可以用来设定某位为1：<code>0b11101010 | 0b00000100</code>等于<code>0b11101110</code>
* [[按位与]]可以用来设定某位为0：<code>0b11101010 & 0b11111101</code>等于<code>0b11101000</code>
* 用[[按位与]]和非零检测可以用来确定某位是否存在
**<code>0b11101010 & 0b00000001</code>是<code>0b00000000</code>，就是false
**<code>0b11101010 & 0b00000010</code>是<code>0b00000010</code>，就是true
* [[按位异或]]可以被用来对某一位取反（这里用<code>^</code>表示异或：
** <code>0b11101010 ^ 0b00000100</code>等于<code>0b11101110</code>
** <code>0b11101110 ^ 0b00000100</code>等于<code>0b11101010</code>
* [[位操作#取反（NOT）|按位非]]可以用来对所有位取反：
**<code>~0b10110010</code>等于<code>0b01001101</code>

为了获得这些操作所需的[[掩码]]，可以用[[位操作#移位|移位运算符]]，把数字<code>1</code>左移合适的位数，若需，再把结果[[位操作#取反（NOT）|按位取反]]。

给定两个长度相同的位数组，我们可以简单地用<math>O\left(\dfrac{n}{w}\right)</math>次运算计算他们的[[并集]]，[[交集]]与[[差集]]，和任意一个的[[补集]]：
<syntaxhighlight lang="text">
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])
</syntaxhighlight>

假如我们希望遍历某个位数组里所有的位，我们可以高效地通过一个遍历位数组里每个字的二层循环，只需要<math>\dfrac{n}{w}</math>次内存访问：
<syntaxhighlight lang="text">
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
</syntaxhighlight>
这几个代码示例都展示了理想的[[访问局部性]]，这又将会获得极大的缓存存取性能提升。如果一个缓存行有k个字，仅会出现大约<math>\dfrac{n}{wk}</math>次缓存不命中。

== 更复杂的运算 ==

像[[字符串]]一样，我们可以很方便的定义位数组的长度，子串，[[字典序]]比较，链接，反转等概念。这些概念中有一部分对[[字节序]]敏感。

=== [[汉明重量]] ===
如果希望查出位数组中1的个数（有时叫人口数或[[汉明重量]]），可以采用一些通过简单[[位运算]]实现的计算每个字里1的数量的无分支的算法。只需要对位数组的每一个字运行这样的算法并求和，就能得到位数组的汉明重量。这样的算法也能用来算出数组中0的个数。

=== 翻转 ===

一像素一位的图片的垂直翻转，或一些[[快速傅里叶变换]]，需要对字里的每一位进行翻转（这样像<code>b31 b30 ... b0</code>这样的序列就变成了<code>b0 ... b30 b31</code>）。
当这处理器没法运行这种字内反转操作的时候，仍然可以完成这样的需求，这里举一个32位的例子

<syntaxhighlight lang="c">
exchange two 16bit 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)).
</syntaxhighlight>

=== 寻找第一位1 ===
“找第一位一”的操作可以确认数组里的第一个1，而且有广泛的硬件支持（对于最长是一个字的数组）和高效的用于计算的算法。当[[先序队列]]储存在位数组里，这种操作可以用来确定队列中的最优先元素。为拓展一字长度的“找第一位一”操作使得其能被用于更长的序列，我们可以找第一个非零字，然后施用这个操作。“找第一位一”，“查前导零”，“查前导一”，“查后导零”，“查后导一”和“以二为底的对数”等相关操作也可以直接延伸到位数组上。

== 压缩 ==

位数组能最紧密地储存随机比特序列，即每一位是0和1的概率相等且任意两位之间无关联的比特序列。但是大多数的数据不是随机的，所以有时候可以存储得更紧密。比如，一个典型的传真图像不是随机的，并且可以压缩。[[游程编码]]在压缩这些长[[字串流|流]]上常常被应用。然而，大多数的压缩信息格式没这么容易随机访问；而且大幅度地压缩位数组也会带来失去位数组位级别并行运算优势的风险（[[阵列编程|矢量化]]）。因此，相对于按[[位元流]]的方式压缩位数组，我们可能按[[字节流]]（或字流）的方式压缩（参见{{link-en|Bitmap index#Compression}}）。

== 优势和劣势 ==
尽管位数组十分简单，但对于特定的使用场景，它仍然能表现出相对于其他数据结构的优越性:
* 位数组是唯一能把<math>n</math>个独立数据存进<math>\frac{n}{w}</math>个字里的数据结构
* 位数组允许在不进行内存访问的情况下将小的位元序列长期存进寄存器集并在其中操作。
* 由于位数组利用位级别并行性的能力，有限的内存访问，和对缓存的最大限度应用，在实际数据集上，它的能力通常超过其他数据结构，甚至是一些复杂度更小的数据结构
然而，位数组也不能用来解决所有问题。比如：
* 不进行压缩的情况下，位数组相对于能在较大区间内存少量元素的离散的集合来说很浪费时间和空间。在这样的场景中，就应该考虑一下[[朱迪矩陣|朱迪矩阵]]，[[字典树]]，或者甚至是[[布隆过滤器]]等结构。
* 在一些编程语言中，对位数组单独元素的访问可能开销很高或者很难实现。如果在实现中随机访问比序列访问更普遍，而且序列相对较小，位数组在可以字节寻址的机器上更好用。然而字数组可能由于其巨大的空间开销和额外的缓存未命中不适用，除非在只有字寻址的机器上。

== 应用 ==
由于位数组的紧凑性，它们在格外需要空间或效率的地方有许多应用。它们通常用在表示一单组布尔标记位或者布尔值的有序序列的情况中。

位数组也可以用在[[先序队列]]里面。这种情况下，当且仅当k在队列里时，第k位才被设置为1. 比如在[[Linux内核]]里就使用了这种数据结构，而且它的能力可以从硬件里的“找首位0”操作中得到很大的提升。

位数组也可以用在[[分页|内存页]]，[[inode]]，磁盘分区等的分配上。这种情况下，可能会用“{{lang|en|bitmap}}”这个术语。（然而bitmap这个词更常用于指代[[位图]]<!-- which may use multiple [[color depth|bits per pixel]] -->）

位数组的另一个应用是[[布隆过滤器]]，一种用小概率产生错误换取很小的空间开销的概率性[[集合]]数据结构。也可以建立基于位数组的可接受正向错误和反向错误的概率性[[散列表]]。

位数组和它们上的操作对于构造希望使用尽可能最小空间的{{link-en|简洁数据结构|Succinct_data_structure}}也很重要。在这种情况下，像找第n个1或者在某个范围内查1的个数的操作就变得十分重要了。

位数组也是用来检查[[数据压缩|压缩过的数据]]流的有用的抽象，压缩数据流中经常包含占用字节部分或未按字节对齐的元素。比如，一个8位字符的[[哈夫曼编码]]的长度可能是1到255位之间的任意值。

在[[信息检索]]中，位数组是常见短语的邻接列表的很好的表示方式。<!--bit arrays are a good representation for the [[posting list]]s of very frequent terms.-->在一个严格递增的整数序列中，如果我们求每两个相邻值之间的差，并且用{{link-en|一元编码|unary coding}}将其编码，结果就是一个当且仅当列表里有n时第n位为1的位数组。一个n位宽的间隔出现的概率是<math>O\left(\dfrac{1}{2^n}\right)</math>。这也是[[格伦布编码]]在参数M为1时的一种特例，这个参数通常只当<math>-\dfrac{\log (2-p)}{log (1-p)} \le 1</math>时被选择，否则文档中就至少会出现38%的这个短语。

== 语言支持 ==
[[APL语言]]提供了对任意形状与大小的位数组的支持，作为一种不同于整形的布尔数据类型。全部主要的实现（Dyalog APL, APL2, APL Next, NARS2000, Gnu APL等等）都会把位元紧凑打包成机器一个字的大小。通过通常的索引表达（如<code>A[3]</code>）或通过常见的基本函数和运算符，可以单独访问每个位，这里通常用像对字节表里位元数求和的特例算法对其进行操作。

[[C语言]]的[[位段]]，结构体中存在的大小是几位的伪对象，事实上就是位数组。位段的长度限制在一字一下。尽管它们提供了一个方便的表达式，位数组在多数的机器上仍然是用位运算符操作的，而且它们也只能被静态定义（像C的静态数组，编译的时候数组的大小就被固定了）。用字来当做小的位数组并且用位运算符对其操作也是C程序员的一种常见用法。在[[X窗口系统|X窗口]]系统中有一个广泛可用的头文件，叫做xtrapbits.h，它是一个“对系统定义位数组的位段操作的可移植的方式”。在[http://c-faq.com/misc/bitsets/html comp.lang.c 常见问题解答]{{Dead link}}里有一份关于上述方法的更详细的描述

在[[C++]]里，尽管单个的布尔变量通常占据一字节或者一个整数的空间，[[标准模板库]]里面的类型<code>vector&lt;bool&gt;</code>就是一个{{link-en|模板部分特化|partial template specialization}}，这里位元为空间效率优化被打包。由于C++中内存的最小单元是字节而不是位元，因此索引运算符''并不''返回对某个元素的引用，相反，它返回的是一个[[代理模式|代理引用]]。这可能看起来没什么大事，但是这意味着<code>vector&lt;bool&gt;</code>不是标准STL容器，也使得它的使用通常不被鼓励。另一个不同的STL类<code>bitset</code><ref name="c++" />，提供了一个长度在编译时固定的位数组，而且它的接口和表达式更贴合C程序员的对位数组的通常用法。位数组也有一些附加的功能，像高效查位数组中1的个数的功能。[[Boost C++ Libraries]]提供了一个<code>dynamic_bitset</code>类<ref name="boost" />，<code>dynamic_bitset</code>的大小在运行时被指定。

[[D语言]]在标准库Phobos里提供了位数组<code>std.bitmanip</code>。像在C++里一样，因为单独的位元在大多数的硬件上没法寻址，索引运算符不会返回引用，但是返回的是一个布尔值。

在[[Java]]里，可以通过{{Javadoc:SE|java/util|BitSet}}构造位数组，这种位数组可以通过C程序员熟悉的位运算的名字操作。不像C++里的bitset，Java里的BitSet不限制大小，在初始化的时候就有无穷位初始为0的位元；可以在任意的索引设定或取值。附加地，Java里还有一个{{Javadoc:SE|java/util|EnumSet}}类，EnumSet作为位数组表示一个枚举里元素的集合，是位段的一个较安全的选择。

[[.NET框架]]提供了一个<code>BitArray</code>收集类。它储存布尔值，支持随机访问和位运算符，可遍历，并且长度可增可减。

尽管[[Standard ML]]没有提供位数组的支持，New Jersey的Standard ML在SML/NJ库里有一个扩展，结构体<code>BitArray</code>。它的大小不固定，而且支持设定操作和位运算，通常包含位移运算。

[[Haskell]]，类似的，目前也缺少位运算的标准支持，但是GHC和Hugs都提供了带有分类的位函数和位运算的<code>Data.Bits</code>模块，模块包含了位移和旋转操作，还有一个可以用来实现位数组的包含布尔值的“未封装的<!-- unboxed -->”数组，尽管它缺乏先前提到的模块的支持。

在[[Perl]]语言里，字符串可以被用作可拓展的位数组。这可以通过通常的位运算符操作（按位非，按位或，按位与，按位异或等）<ref>{{cite web|url=http://perldoc.perl.org/perlop.html#Bitwise-String-Operators|title=perlop - perldoc.perl.org|website=perldoc.perl.org|accessdate=2020-06-25|archive-date=2012-07-17|archive-url=https://web.archive.org/web/20120717041740/http://perldoc.perl.org/perlop.html#Bitwise-String-Operators|dead-url=no}}</ref>，并且单独的位元可以通过函数<code>vec</code>检查并设定值<ref>{{cite web|url=http://perldoc.perl.org/functions/vec.html|title=vec - perldoc.perl.org|website=perldoc.perl.org|accessdate=2020-06-25|archive-date=2020-06-30|archive-url=https://web.archive.org/web/20200630214751/https://perldoc.perl.org/functions/vec.html|dead-url=no}}</ref>。

在[[Ruby]]里，可以用方括号运算符（<code>[]</code>）像位数组一样访问（但不能设定）一个整数（<code>Fixnum</code>或<code>Bignum</code>）的一位。

苹果的{{link-en|Core Foundation}}库包含了[https://developer.apple.com/library/mac/#documentation/CoreFoundation/Reference/CFBitVectorRef/Reference/reference.html CFBitVector]{{Wayback|url=https://developer.apple.com/library/mac/#documentation/CoreFoundation/Reference/CFBitVectorRef/Reference/reference.html |date=20120609170929 }}和[https://developer.apple.com/library/mac/#documentation/CoreFoundation/Reference/CFMutableBitVectorRef/Reference/reference.html#//apple_ref/doc/uid/20001500 CFMutableBitVector]{{Wayback|url=https://developer.apple.com/library/mac/#documentation/CoreFoundation/Reference/CFMutableBitVectorRef/Reference/reference.html |date=20120609170929 }}结构体。

[[PL/I]]支持任意长度的位字符串数组，长度可能固定可能变化。数组的元素可能是对齐的（每个元素在字节或字的开始对齐）或者不对齐（元素之间紧挨着，没有间隔）

[[PL/pgSQL]]和PostgreSQL's SQL支持位字符串作为内置类。SQL有两种位元类：<code>bit(n)</code>和<code>bit varying(n)</code>（n是正整数）<ref>{{Cite web |url=https://www.postgresql.org/docs/current/datatype-bit.html |title=存档副本 |accessdate=2020-06-25 |archive-date=2020-05-14 |archive-url=https://web.archive.org/web/20200514010034/https://www.postgresql.org/docs/current/datatype-bit.html |dead-url=no }}</ref>。

像[[VHDL]], [[Verilog]]和[[SystemVerilog]]的硬件描述语言内置了用于实现像[[触发器]]一样的内存元素的位数组，普遍是硬件总线和硬件信号。在像[[OpenVera]]，[[E语言]]和[[SystemVerilog]]之类的硬件验证语言，位数组悲用来从硬件模型中抽样，并表示模拟时转移到硬件的数据。

== 参见 ==
* [[二进制编码]]
* [[位段]]
* [[算数逻辑单元]]
* {{link-en|位版|bitboard}} 棋类游戏。
* {{link-en|位图索引|Bitmap index}}
* [[二进制]]
* [[位元流]]
* [[朱迪矩陣|朱迪矩阵]]

== 参考 ==
{{Reflist | refs =
<ref name="c++">{{cite web|url=http://www.sgi.com/tech/stl/bitset.html|title=SGI.com Tech Archive Resources now retired|date=2 January 2018|publisher=[[Silicon Graphics|SGI]]|accessdate=2020-06-25|archive-date=2018-01-01|archive-url=https://web.archive.org/web/20180101052335/http://www.sgi.com/tech/stl/bitset.html|dead-url=no}}</ref>
<ref name="boost">{{cite web|url=http://www.boost.org/libs/dynamic_bitset/dynamic_bitset.html|title=dynamic_bitset<Block, Allocator> - 1.66.0|website=www.boost.org|accessdate=2020-06-25|archive-date=2008-09-06|archive-url=https://web.archive.org/web/20080906153034/http://www.boost.org/libs/dynamic_bitset/dynamic_bitset.html|dead-url=no}}</ref>
}}

== 外部链接 ==
* [http://www-cs-faculty.stanford.edu/~knuth/fasc1a.ps.gz mathematical bases]{{Wayback|url=http://www-cs-faculty.stanford.edu/~knuth/fasc1a.ps.gz |date=20191016044101 }} by Pr. D.E.Knuth
* [http://www.gotw.ca/publications/N1185.pdf vector&lt;bool&gt; Is Nonconforming, and Forces Optimization Choice]{{Wayback|url=http://www.gotw.ca/publications/N1185.pdf |date=20180628050210 }}
* [http://www.gotw.ca/publications/N1211.pdf vector&lt;bool&gt;: More Problems, Better Solutions]{{Wayback|url=http://www.gotw.ca/publications/N1211.pdf |date=20120812221344 }}

{{数据结构}}

[[Category:数组]]
[[Category:位数据结构]]