位數組
 |
位數組（英語：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）.
外部連結[編輯]
- mathematical bases（頁面存檔備份，存於網際網路檔案館） by Pr. D.E.Knuth
- vector<bool> Is Nonconforming, and Forces Optimization Choice（頁面存檔備份，存於網際網路檔案館）
- vector<bool>: More Problems, Better Solutions（頁面存檔備份，存於網際網路檔案館）
| |||||||||||||||||||||||||||||||||||||