位陣列
 |
位陣列（英語：bit array），是一種能夠緊湊地儲存位的陣列。位陣列可以被用來實現簡單的有限集合。它能夠通過硬體中位級別的並列運算快速操作。通常情況下，一個位陣列可以儲存位資訊（w是硬體中單個儲存單元的位數，如位元組或字，而k是一非負整數），如果w不能被電腦中儲存單位的位元組數整除，就會由於主記憶體碎片化浪費一些主記憶體空間。
定義
[編輯]位陣列可以看作某個集合到的對映。其中的每個值可以解釋做燈泡的明暗，元素的有無等等。因為每一個值只有兩種可能性，所以能夠把每個值儲存進一位的主記憶體。與其他種類的陣列對應地，可以通過對陣列應用索引的方式操作單個位元。假設某個位陣列的大小是位，那麼這個陣列就可以用來表示一個包含個元素的集合（比如）的子集，在每個位置上用表示對應元素存在，表示其不存在。這種資料結構占用的空間（表示電腦里一個字的位數）。使用最高位還是最低位代表最小索引不會造成什麼影響，但通常在小端序的機器上的實現偏向前者。
基本操作
[編輯]儘管大多數的機器不能在主記憶體中定位單個的位，也沒有操作單個位的指令，字裡的每一位仍然可以用位元運算分離並單獨操作。比如：
- 按位元或可以用來設定某位為1：
0b11101010 | 0b00000100等於0b11101110 - 按位元與可以用來設定某位為0：
0b11101010 & 0b11111101等於0b11101000 - 用按位元與和非零檢測可以用來確定某位是否存在
0b11101010 & 0b00000001是0b00000000，就是false0b11101010 & 0b00000010是0b00000010，就是true
- 按位元互斥或可以被用來對某一位取反（這裡用
^表示互斥或：0b11101010 ^ 0b00000100等於0b111011100b11101110 ^ 0b00000100等於0b11101010
- 按位元非可以用來對所有位取反：
~0b10110010等於0b01001101
為了獲得這些操作所需的遮罩，可以用移位元運算符，把數字1左移合適的位數，若需，再把結果按位元取反。
給定兩個長度相同的位陣列，我們可以簡單地用次運算計算他們的併集，交集與差集，和任意一個的補集：
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])
假如我們希望遍歷某個位陣列里所有的位，我們可以高效地通過一個遍歷位陣列里每個字的二層迴圈，只需要次主記憶體訪問：
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
這幾個代碼範例都展示了理想的訪問局部性，這又將會獲得極大的快取存取效能提升。如果一個快取行有k個字，僅會出現大約次快取不命中。
更複雜的運算
[編輯]像字串一樣，我們可以很方便的定義位陣列的長度，子串，字典序比較，連結，反轉等概念。這些概念中有一部分對位元組序敏感。
如果希望查出位陣列中1的個數（有時叫人口數或漢明重量），可以採用一些通過簡單位元運算實現的計算每個字裡1的數量的無分支的演算法。只需要對位陣列的每一個字執行這樣的演算法並求和，就能得到位陣列的漢明重量。這樣的演算法也能用來算出陣列中0的個數。
翻轉
[編輯]一像素一位的圖片的垂直翻轉，或一些快速傅立葉變換，需要對字裡的每一位進行翻轉（這樣像b31 b30 ... b0這樣的序列就變成了b0 ... b30 b31）。
當這處理器沒法執行這種字內反轉操作的時候，仍然可以完成這樣的需求，這裡舉一個32位元的例子
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)).
尋找第一位1
[編輯]「找第一位一」的操作可以確認陣列里的第一個1，而且有廣泛的硬體支援（對於最長是一個字的陣列）和高效的用於計算的演算法。當先序佇列儲存在位陣列里，這種操作可以用來確定佇列中的最優先元素。為拓展一字長度的「找第一位一」操作使得其能被用於更長的序列，我們可以找第一個非零字，然後施用這個操作。「找第一位一」，「查前導零」，「查前導一」，「查後導零」，「查後導一」和「以二為底的對數」等相關操作也可以直接延伸到位陣列上。
壓縮
[編輯]位陣列能最緊密地儲存隨機位元序列，即每一位是0和1的概率相等且任意兩位之間無關聯的位元序列。但是大多數的資料不是隨機的，所以有時候可以儲存得更緊密。比如，一個典型的傳真圖像不是隨機的，並且可以壓縮。遊程編碼在壓縮這些長流上常常被應用。然而，大多數的壓縮資訊格式沒這麼容易隨機訪問；而且大幅度地壓縮位陣列也會帶來失去位陣列位級別並列運算優勢的風險（向量化）。因此，相對於按位元流的方式壓縮位陣列，我們可能按位元組流（或字流）的方式壓縮（參見Bitmap index#Compression）。
優勢和劣勢
[編輯]儘管位陣列十分簡單，但對於特定的使用場景，它仍然能表現出相對於其他資料結構的優越性:
- 位陣列是唯一能把個獨立資料存進個字裡的資料結構
- 位陣列允許在不進行主記憶體訪問的情況下將小的位元序列長期存進暫存器集並在其中操作。
- 由於位陣列利用位級別並列性的能力，有限的主記憶體訪問，和對快取的最大限度應用，在實際資料集上，它的能力通常超過其他資料結構，甚至是一些複雜度更小的資料結構
然而，位陣列也不能用來解決所有問題。比如：
- 不進行壓縮的情況下，位陣列相對於能在較大區間主記憶體少量元素的離散的集合來說很浪費時間和空間。在這樣的場景中，就應該考慮一下朱迪矩陣，字典樹，或者甚至是布隆過濾器等結構。
- 在一些程式語言中，對位陣列單獨元素的訪問可能開銷很高或者很難實現。如果在實現中隨機訪問比序列訪問更普遍，而且序列相對較小，位陣列在可以位元組定址的機器上更好用。然而字陣列可能由於其巨大的空間開銷和額外的快取未命中不適用，除非在只有字定址的機器上。
應用
[編輯]由於位陣列的緊湊性，它們在格外需要空間或效率的地方有許多應用。它們通常用在表示一單組布林標記位或者布林值的有序序列的情況中。
位陣列也可以用在先序佇列裡面。這種情況下，若且唯若k在佇列里時，第k位才被設定為1. 比如在Linux核心里就使用了這種資料結構，而且它的能力可以從硬體里的「找首位0」操作中得到很大的提升。
位陣列也可以用在主記憶體頁，inode，磁碟分割區等的分配上。這種情況下，可能會用「bitmap」這個術語。（然而bitmap這個詞更常用於指代點陣圖）
位陣列的另一個應用是布隆過濾器，一種用小概率產生錯誤換取很小的空間開銷的概率性集合資料結構。也可以建立基於位陣列的可接受正向錯誤和反向錯誤的概率性雜湊表。
位陣列和它們上的操作對於構造希望使用儘可能最小空間的簡潔資料結構也很重要。在這種情況下，像找第n個1或者在某個範圍內查1的個數的操作就變得十分重要了。
位陣列也是用來檢查壓縮過的資料流的有用的抽象，壓縮資料流中經常包含占用位元組部分或未按位元組對齊的元素。比如，一個8位元字元的哈夫曼編碼的長度可能是1到255位之間的任意值。
在資訊檢索中，位陣列是常見短語的鄰接列表的很好的表示方式。在一個嚴格遞增的整數序列中，如果我們求每兩個相鄰值之間的差，並且用一元編碼將其編碼，結果就是一個若且唯若列表里有n時第n位為1的位陣列。一個n位寬的間隔出現的概率是。這也是格倫布編碼在參數M為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[1]，提供了一個長度在編譯時固定的位陣列，而且它的介面和表達式更貼合C程式設計師的對位陣列的通常用法。位陣列也有一些附加的功能，像高效查位陣列中1的個數的功能。Boost C++ Libraries提供了一個dynamic_bitset類[2]，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語言裡，字串可以被用作可拓展的位陣列。這可以通過通常的位元運算符操作（按位元非，按位元或，按位元與，按位元互斥或等）[3]，並且單獨的位元可以通過函式vec檢查並設定值[4]。
在Ruby里，可以用方括號運算子（[]）像位陣列一樣訪問（但不能設定）一個整數（Fixnum或Bignum）的一位。
蘋果的Core Foundation庫包含了CFBitVector（頁面存檔備份，存於網際網路檔案館）和CFMutableBitVector（頁面存檔備份，存於網際網路檔案館）結構體。
PL/I支援任意長度的位字串陣列，長度可能固定可能變化。陣列的元素可能是對齊的（每個元素在位元組或字的開始對齊）或者不對齊（元素之間緊挨著，沒有間隔）
PL/pgSQL和PostgreSQL's SQL支援位字串作為內建類。SQL有兩種位元類：bit(n)和bit varying(n)（n是正整數）[5]。
像VHDL, Verilog和SystemVerilog的硬體描述語言內建了用於實現像觸發器一樣的主記憶體元素的位陣列，普遍是硬體匯流排和硬體訊號。在像OpenVera，E語言和SystemVerilog之類的硬體驗證語言，位陣列悲用來從硬體模型中抽樣，並表示類比時轉移到硬體的資料。
參見
[編輯]參考
[編輯]- ^ SGI.com Tech Archive Resources now retired. SGI. 2 January 2018 [2020-06-25]. （原始內容存檔於2018-01-01）.
- ^ dynamic_bitset<Block, Allocator> - 1.66.0. www.boost.org. [2020-06-25]. （原始內容存檔於2008-09-06）.
- ^ perlop - perldoc.perl.org. perldoc.perl.org. [2020-06-25]. （原始內容存檔於2012-07-17）.
- ^ vec - perldoc.perl.org. perldoc.perl.org. [2020-06-25]. （原始內容存檔於2020-06-30）.
- ^ 存档副本. [2020-06-25]. （原始內容存檔於2020-05-14）.