位陣列

**位陣列**（英語：bit array），是一種能夠緊湊地儲存位的陣列。位陣列可以被用來實現簡單的集合。它能夠通過硬體中位級別的並列運算快速操作。通常情況下，一個位陣列可以儲存 $kw$ 位資訊（w 是硬體中單個儲存單元的位數，如位元組或字，而 k 是一非負整數），如果 w 不能被電腦中儲存單位的位元組數整除，就會由於記憶體碎片化浪費一些記憶體空間。

## 定義

位陣列可以看作某個集合到 $\{0,1\}$ 的對映。其中的每個值可以解釋做燈泡的明暗，元素的有無等等。因為每一個值只有兩種可能性，所以能夠把每個值儲存進一位的記憶體。與其他種類的陣列對應地，可以通過對陣列應用索引的方式操作單個位元。假設某個位陣列的大小是 $n$ 位，那麼這個陣列就可以用來表示一個包含 $n$ 個元素的集合（比如 $[0,n)\cap N$ ）的子集，在每個位置上用 $1$ 表示對應元素存在， $0$ 表示其不存在。這種資料結構占用 $O\left({\dfrac {n}{w}}\right)$ 的空間（ $w$ 表示電腦里一個字的位數）。使用最高位還是最低位代表最小索引不會造成什麼影響，但通常在小端序的機器上的實現偏向前者。

## 基本操作

儘管大多數的機器不能在記憶體中定位單個的位，也沒有操作單個位的指令，字裡的每一位仍然可以用位元運算分離並單獨操作。比如：

* 按位元或可以用來設定某位為 1：`0b11101010 | 0b00000100` 等於 `0b11101110`
* 按位元與可以用來設定某位為 0：`0b11101010 & 0b11111101` 等於 `0b11101000`
* 用按位元與和非零檢測可以用來確定某位是否存在
  * `0b11101010 & 0b00000001` 是 `0b00000000`，就是 false
  * `0b11101010 & 0b00000010` 是 `0b00000010`，就是 true
* 按位元互斥或可以被用來對某一位取反（這裡用 `^` 表示互斥或：
  * `0b11101010 ^ 0b00000100` 等於 `0b11101110`
  * `0b11101110 ^ 0b00000100` 等於 `0b11101010`
* 按位元非可以用來對所有位取反：
  * `~0b10110010` 等於 `0b01001101`

為了獲得這些操作所需的遮罩，可以用移位元運算符，把數字 `1` 左移合適的位數，若需，再把結果按位元取反。

給定兩個長度相同的位陣列，我們可以簡單地用 $O\left({\dfrac {n}{w}}\right)$ 次運算計算他們的併集，交集與差集，和任意一個的補集：

假如我們希望遍歷某個位陣列里所有的位，我們可以高效地通過一個遍歷位陣列里每個字的二層迴圈，只需要 ${\dfrac {n}{w}}$ 次記憶體存取：

這幾個代碼範例都展示了理想的存取局部性，這又將會獲得極大的快取存取效能提升。如果一個快取行有 k 個字，僅會出現大約 ${\dfrac {n}{wk}}$ 次快取不命中。

## 更複雜的運算

像字串一樣，我們可以很方便的定義位陣列的長度，子串，字典序比較，連結，反轉等概念。這些概念中有一部分對位元組序敏感。

### 漢明重量

如果希望查出位陣列中 1 的個數（有時叫人口數或漢明重量），可以採用一些通過簡單位元運算實現的計算每個字裡 1 的數量的無分支的演算法。只需要對位陣列的每一個字執行這樣的演算法並求和，就能得到位陣列的漢明重量。這樣的演算法也能用來算出陣列中 0 的個數。

### 翻轉

一像素一位的圖片的垂直翻轉，或一些快速傅立葉變換，需要對字裡的每一位進行翻轉（這樣像 `b31 b30 ... b0` 這樣的序列就變成了 `b0 ... b30 b31`）。
當這處理器沒法執行這種字內反轉操作的時候，仍然可以完成這樣的需求，這裡舉一個 32 位元的例子

### 尋找第一位 1

「找第一位一」的操作可以確認陣列里的第一個 1，而且有廣泛的硬體支援（對於最長是一個字的陣列）和高效的用於計算的演算法。當先序佇列儲存在位陣列里，這種操作可以用來確定佇列中的最優先元素。為拓展一字長度的「找第一位一」操作使得其能被用於更長的序列，我們可以找第一個非零字，然後施用這個操作。「找第一位一」，「查前導零」，「查前導一」，「查後導零」，「查後導一」和「以二為底的對數」等相關操作也可以直接延伸到位陣列上。

## 壓縮

位陣列能最緊密地儲存隨機位元序列，即每一位是 0 和 1 的概率相等且任意兩位之間無關聯的位元序列。但是大多數的資料不是隨機的，所以有時候可以儲存得更緊密。比如，一個典型的傳真圖像不是隨機的，並且可以壓縮。遊程編碼在壓縮這些長流上常常被應用。然而，大多數的壓縮資訊格式沒這麼容易隨機存取；而且大幅度地壓縮位陣列也會帶來失去位陣列位級別並列運算優勢的風險（向量化）。因此，相對於按位元流的方式壓縮位陣列，我們可能按位元組流（或字流）的方式壓縮（參見 Bitmap index#Compression）。

## 優勢和劣勢

儘管位陣列十分簡單，但對於特定的使用場景，它仍然能表現出相對於其他資料結構的優越性:

* 位陣列是唯一能把 $n$ 個獨立資料存進 ${\frac {n}{w}}$ 個字裡的資料結構
* 位陣列允許在不進行記憶體存取的情況下將小的位元序列長期存進暫存器集並在其中操作。
* 由於位陣列利用位級別並列性的能力，有限的記憶體存取，和對快取的最大限度應用，在實際資料集上，它的能力通常超過其他資料結構，甚至是一些複雜度更小的資料結構

然而，位陣列也不能用來解決所有問題。比如：

* 不進行壓縮的情況下，位陣列相對於能在較大區間記憶體少量元素的離散的集合來說很浪費時間和空間。在這樣的場景中，就應該考慮一下朱迪矩陣，字典樹，或者甚至是布隆過濾器等結構。
* 在一些程式語言中，對位陣列單獨元素的存取可能開銷很高或者很難實現。如果在實現中隨機存取比序列存取更普遍，而且序列相對較小，位陣列在可以位元組定址的機器上更好用。然而字陣列可能由於其巨大的空間開銷和額外的快取未命中不適用，除非在只有字定址的機器上。

## 應用

由於位陣列的緊湊性，它們在格外需要空間或效率的地方有許多應用。它們通常用在表示一單組布林標記位或者布林值的有序序列的情況中。

位陣列也可以用在先序佇列裡面。這種情況下，若且唯若 k 在佇列里時，第 k 位才被設定為 1. 比如在 Linux 核心里就使用了這種資料結構，而且它的能力可以從硬體里的「找首位 0」操作中得到很大的提升。

位陣列也可以用在記憶體頁，inode，磁碟分割區等的分配上。這種情況下，可能會用「bitmap」這個術語。（然而 bitmap 這個詞更常用於指代點陣圖）

位陣列的另一個應用是布隆過濾器，一種用小概率產生錯誤換取很小的空間開銷的概率性集合資料結構。也可以建立基於位陣列的可接受正向錯誤和反向錯誤的概率性雜湊表。

位陣列和它們上的操作對於構造希望使用儘可能最小空間的簡潔資料結構也很重要。在這種情況下，像找第 n 個 1 或者在某個範圍內查 1 的個數的操作就變得十分重要了。

位陣列也是用來檢查壓縮過的資料流的有用的抽象，壓縮資料流中經常包含占用位元組部分或未按位元組對齊的元素。比如，一個 8 位元字元的哈夫曼編碼的長度可能是 1 到 255 位之間的任意值。

在資訊檢索中，位陣列是常見短語的鄰接列表的很好的表示方式。在一個嚴格遞增的整數序列中，如果我們求每兩個相鄰值之間的差，並且用一元編碼將其編碼，結果就是一個若且唯若列表里有 n 時第 n 位為 1 的位陣列。一個 n 位寬的間隔出現的概率是 $O\left({\dfrac {1}{2^{n}}}\right)$ 。這也是格倫布編碼在參數 M 為 1 時的一種特例，這個參數通常只當 $-{\dfrac {\log(2-p)}{log(1-p)}}\leq 1$ 時被選擇，否則文件中就至少會出現 38% 的這個短語。

## 語言支援

APL 語言提供了對任意形狀與大小的位陣列的支援，作為一種不同於整形的布林資料類型。全部主要的實現（Dyalog APL, APL2, APL Next, NARS2000, Gnu APL 等等）都會把位元緊湊打包成機器一個字的大小。通過通常的索引表達（如 `A[3]`）或通過常見的基本函式和運算子，可以單獨存取每個位，這裡通常用像對位元組表里位元數求和的特例演算法對其進行操作。

C 語言的位元欄，結構體中存在的大小是幾位的偽物件，事實上就是位陣列。位元欄的長度限制在一字一下。儘管它們提供了一個方便的表達式，位陣列在多數的機器上仍然是用位元運算符操作的，而且它們也只能被靜態定義（像 C 的靜態陣列，編譯的時候陣列的大小就被固定了）。用字來當做小的位陣列並且用位元運算符對其操作也是 C 程式設計師的一種常見用法。在 X 窗口系統中有一個廣泛可用的標頭檔，叫做 xtrapbits.h，它是一個「對系統定義位陣列的位元欄操作的可移植的方式」。在 comp.lang.c 常見問題解答里有一份關於上述方法的更詳細的描述

在 C++ 里，儘管單個的布林變數通常占據一位元組或者一個整數的空間，標準模板庫裡面的類型 `vector<bool>` 就是一個模板部分特化，這裡位元為空間效率最佳化被打包。由於 C++ 中記憶體的最小單元是位元組而不是位元，因此索引運算子_並不_返回對某個元素的參照，相反，它返回的是一個代理參照。這可能看起來沒什麼大事，但是這意味著 `vector<bool>` 不是標準 STL 容器，也使得它的使用通常不被鼓勵。另一個不同的 STL 類 `bitset`，提供了一個長度在編譯時固定的位陣列，而且它的介面和表達式更貼合 C 程式設計師的對位陣列的通常用法。位陣列也有一些附加的功能，像高效查位陣列中 1 的個數的功能。Boost C++ Libraries 提供了一個 `dynamic_bitset` 類，`dynamic_bitset` 的大小在執行時被指定。

D 語言在標準庫 Phobos 里提供了位陣列 `std.bitmanip`。像在 C++ 里一樣，因為單獨的位元在大多數的硬體上沒法定址，索引運算子不會返回參照，但是返回的是一個布林值。

在 Java 里，可以通過 `BitSet` 構造位陣列，這種位陣列可以通過 C 程式設計師熟悉的位元運算的名字操作。不像 C++ 里的 bitset，Java 里的 BitSet 不限制大小，在初始化的時候就有無窮位初始為 0 的位元；可以在任意的索引設定或取值。附加地，Java 里還有一個 `EnumSet` 類，EnumSet 作為位陣列表示一個列舉里元素的集合，是位元欄的一個較安全的選擇。

.NET 框架提供了一個 `BitArray` 收集類。它儲存布林值，支援隨機存取和位元運算符，可遍歷，並且長度可增可減。

儘管 Standard ML 沒有提供位陣列的支援，New Jersey 的 Standard ML 在 SML/NJ 庫里有一個擴充，結構體 `BitArray`。它的大小不固定，而且支援設定操作和位元運算，通常包含位移運算。

Haskell，類似的，目前也缺少位元運算的標準支援，但是 GHC 和 Hugs 都提供了帶有分類的位函式和位元運算的 `Data.Bits` 模組，模組包含了位移和旋轉操作，還有一個可以用來實現位陣列的包含布林值的「未封裝的」陣列，儘管它缺乏先前提到的模組的支援。

在 Perl 語言裡，字串可以被用作可拓展的位陣列。這可以通過通常的位元運算符操作（按位元非，按位元或，按位元與，按位元互斥或等），並且單獨的位元可以通過函式 `vec` 檢查並設定值。

在 Ruby 里，可以用方括號運算子（`[]`）像位陣列一樣存取（但不能設定）一個整數（`Fixnum` 或 `Bignum`）的一位。

蘋果的 Core Foundation 庫包含了 CFBitVector（頁面存檔備份，存於網際網路檔案館）和 CFMutableBitVector（頁面存檔備份，存於網際網路檔案館）結構體。

PL/I 支援任意長度的位字串陣列，長度可能固定可能變化。陣列的元素可能是對齊的（每個元素在位元組或字的開始對齊）或者不對齊（元素之間緊挨著，沒有間隔）

PL/pgSQL 和 PostgreSQL's SQL 支援位字串作為內建類。SQL 有兩種位元類：`bit(n)` 和 `bit varying(n)`（n 是正整數）。

像 VHDL, Verilog 和 SystemVerilog 的硬體描述語言內建了用於實現像觸發器一樣的記憶體元素的位陣列，普遍是硬體匯流排和硬體訊號。在像 OpenVera，E 語言和 SystemVerilog 之類的硬體驗證語言，位陣列悲用來從硬體模型中抽樣，並表示類比時轉移到硬體的資料。

## 參見

* 二進位編碼
* 位元欄
* 算數邏輯單元
* 位版 棋類遊戲。
* 點陣圖索引
* 二進位
* 位元流
* 朱迪矩陣

## 參考

## 外部連結

* mathematical bases（頁面存檔備份，存於網際網路檔案館） by Pr. D.E.Knuth
* vector<bool> Is Nonconforming, and Forces Optimization Choice（頁面存檔備份，存於網際網路檔案館）
* vector<bool>: More Problems, Better Solutions（頁面存檔備份，存於網際網路檔案館）