位陣列

位陣列，如果w不能被計算機中儲存單位的位元組數整除，就會由於記憶體碎片化浪費一些記憶體空間。定義.位陣列可以看作某個集合到formula_2的對映。其中的每個值可以解釋做燈泡的明暗，元素的有無等等。因為每一個值只有兩種可能性，所以能夠把每個值儲存進一位的記憶體。與其他種類的陣列對應地，可以透過對陣列應用索引的方式操作單個位元。假設某個位陣列的大小是formula_3位，那麼這個陣列就可以用來表示一個包含formula_3個元素的集合。使用最高位還是最低位代表最小索引不會造成什麼影響，但通常在小端序的機器上的實現偏向前者。基本操作.儘管大多數的機器不能在記憶體中定位單個的位，也沒有操作單個位的指令，字裡的每一位仍然可以用位運算分離並單獨操作。比如：為了獲得這些操作所需的掩碼，可以用移位運算子，把數字codice_16左移合適的位數，若需，再把結果按位取反。給定兩個長度相同的位陣列，我們可以簡單地用formula_8次運算計算他們的並集，交集與差集，和任意一個的補集：for i from 0 to n/w-1complement_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])假如我們希望遍歷某個位數組裡所有的位，我們可以高效地透過一個遍歷位數組裡每個字的二層迴圈，只需要formula_11次記憶體訪問：for i from 0 to n/w-1index := 0 // if neededword := a[i]for b from 0 to w-1value := word and 1 ≠ 0word := word shift right 1// do something with valueindex := index + 1 // if needed這幾個程式碼示例都展示了理想的訪問區域性性，這又將會獲得極大的快取存取效能提升。如果一個快取行有k個字，僅會出現大約formula_12次快取不命中。更復雜的運算.像字串一樣，我們可以很方便的定義位陣列的長度，子串，字典序比較，連結，反轉等概念。這些概念中有一部分對位元組序敏感。漢明重量.如果希望查出位陣列中1的個數，可以採用一些透過簡單位運算實現的計算每個字裡1的數量的無分支的演算法。只需要對位陣列的每一個字執行這樣的演算法並求和，就能得到位陣列的漢明重量。這樣的演算法也能用來算出陣列中0的個數。翻轉.一畫素一位的圖片的垂直翻轉，或一些快速傅立葉變換，需要對字裡的每一位進行翻轉。當這處理器沒法執行這種字內反轉操作的時候，仍然可以完成這樣的需求，這裡舉一個32位的例子exchange two 16bit halfwordsexchange bytes by pairs (0xddccbbaa -&gt; 0xccddaabb)swap bits by pairsswap bits (b31 b30 ... b1 b0 -&gt; b30 b31 ... b0 b1)The last operation can be written ((x&amp;0x55555555)«1) | (x&amp;0xaaaaaaaa)»1)).尋找第一位1.“找第一位一”的操作可以確認數組裡的第一個1，而且有廣泛的硬體支援和高效的用於計算的演算法。當先序佇列儲存在位數組裡，這種操作可以用來確定佇列中的最優先元素。為拓展一字長度的“找第一位一”操作使得其能被用於更長的序列，我們可以找第一個非零字，然後施用這個操作。“找第一位一”，“查前導零”，“查前導一”，“查後導零”，“查後導一”和“以二為底的對數”等相關操作也可以直接延伸到位陣列上。壓縮.位陣列能最緊密地儲存隨機位元序列，即每一位是0和1的機率相等且任意兩位之間無關聯的位元序列。但是大多數的資料不是隨機的，所以有時候可以儲存得更緊密。比如，一個典型的傳真影象不是隨機的，並且可以壓縮。遊程編碼在壓縮這些長流上常常被應用。然而，大多數的壓縮資訊格式沒這麼容易隨機訪問；而且大幅度地壓縮位陣列也會帶來失去位陣列位級別並行運算優勢的風險。優勢和劣勢.儘管位陣列十分簡單，但對於特定的使用場景，它仍然能表現出相對於其他資料結構的優越性:然而，位陣列也不能用來解決所有問題。比如：應用.由於位陣列的緊湊性，它們在格外需要空間或效率的地方有許多應用。它們通常用在表示一單組布林標記位或者布林值的有序序列的情況中。位陣列也可以用在先序佇列裡面。這種情況下，當且僅當k在佇列裡時，第k位才被設定為1. 比如在Linux核心裡就使用了這種資料結構，而且它的能力可以從硬體裡的“找首位0”操作中得到很大的提升。位陣列也可以用在記憶體頁，inode，磁碟分割槽等的分配上。這種情況下，可能會用“--”這個術語。位陣列的另一個應用是布隆過濾器，一種用小機率產生錯誤換取很小的空間開銷的機率性集合資料結構。也可以建立基於位陣列的可接受正向錯誤和反向錯誤的機率性散列表。位陣列和它們上的操作對於構造希望使用盡可能最小空間的也很重要。在這種情況下，像找第n個1或者在某個範圍內查1的個數的操作就變得十分重要了。位陣列也是用來檢查壓縮過的資料流的有用的抽象，壓縮資料流中經常包含佔用位元組部分或未按位元組對齊的元素。比如，一個8位字元的哈夫曼編碼的長度可能是1到255位之間的任意值。在資訊檢索中，位陣列是常見短語的鄰接列表的很好的表示方式。在一個嚴格遞增的整數序列中，如果我們求每兩個相鄰值之間的差，並且用將其編碼，結果就是一個當且僅當列表裡有n時第n位為1的位陣列。一個n位寬的間隔出現的機率是formula_15。這也是格倫布編碼在引數M為1時的一種特例，這個引數通常只當formula_16時被選擇，否則文件中就至少會出現38%的這個短語。語言支援.APL語言提供了對任意形狀與大小的位陣列的支援，作為一種不同於整形的布林資料型別。全部主要的實現或透過常見的基本函式和運算子，可以單獨訪問每個位，這裡通常用像對位元組表裡位元數求和的特例演算法對其進行操作。C語言的位段，結構體中存在的大小是幾位的偽物件，事實上就是位陣列。位段的長度限制在一字一下。儘管它們提供了一個方便的表示式，位陣列在多數的機器上仍然是用位運算子操作的，而且它們也只能被靜態定義。用字來當做小的位陣列並且用位運算子對其操作也是C程式設計師的一種常見用法。在X視窗系統中有一個廣泛可用的標頭檔案，叫做xtrapbits.h，它是一個“對系統定義位陣列的位段操作的可移植的方式”。在comp.lang.c 常見問題解答裡有一份關於上述方法的更詳細的描述在C++裡，儘管單個的布林變數通常佔據一位元組或者一個整數的空間，標準模板庫裡面的型別codice_20就是一個，這裡位元為空間效率最佳化被打包。由於C++中記憶體的最小單元是位元組而不是位元，因此索引運算子"並不"返回對某個元素的引用，相反，它返回的是一個代理引用。這可能看起來沒什麼大事，但是這意味著codice_20不是標準STL容器，也使得它的使用通常不被鼓勵。另一個不同的STL類codice_22，提供了一個長度在編譯時固定的位陣列，而且它的介面和表示式更貼合C程式設計師的對位陣列的通常用法。位陣列也有一些附加的功能，像高效查位陣列中1的個數的功能。Boost C++ Libraries提供了一個codice_23類，codice_23的大小在執行時被指定。D語言在標準庫Phobos裡提供了位陣列codice_25。像在C++裡一樣，因為單獨的位元在大多數的硬體上沒法定址，索引運算子不會返回引用，但是返回的是一個布林值。在Java裡，可以透過構造位陣列，這種位陣列可以透過C程式設計師熟悉的位運算的名字操作。不像C++裡的bitset，Java裡的BitSet不限制大小，在初始化的時候就有無窮位初始為0的位元；可以在任意的索引設定或取值。附加地，Java裡還有一個類，EnumSet作為位陣列表示一個列舉裡元素的集合，是位段的一個較安全的選擇。.NET框架提供了一個codice_26收集類。它儲存布林值，支援隨機訪問和位運算子，可遍歷，並且長度可增可減。儘管Standard ML沒有提供位陣列的支援，New Jersey的Standard ML在SML/NJ庫裡有一個擴充套件，結構體codice_26。它的大小不固定，而且支援設定操作和位運算，通常包含位移運算。Haskell，類似的，目前也缺少位運算的標準支援，但是GHC和Hugs都提供了帶有分類的位函式和位運算的codice_28模組，模組包含了位移和旋轉操作，還有一個可以用來實現位陣列的包含布林值的“未封裝的”陣列，儘管它缺乏先前提到的模組的支援。在Perl語言裡，字串可以被用作可拓展的位陣列。這可以透過通常的位運算子操作，並且單獨的位元可以透過函式codice_29檢查並設定值。在Ruby裡，可以用方括號運算子的一位。蘋果的庫包含了CFBitVector結構體。PL/I支援任意長度的位字串陣列，長度可能固定可能變化。陣列的元素可能是對齊的PL/pgSQL和PostgreSQL's SQL支援位字串作為內建類。SQL有兩種位元類：codice_33和codice_34。像VHDL, Verilog和SystemVerilog的硬體描述語言內建了用於實現像觸發器一樣的記憶體元素的位陣列，普遍是硬體匯流排和硬體訊號。在像OpenVera，E語言和SystemVerilog之類的硬體驗證語言，位陣列悲用來從硬體模型中抽樣，並表示模擬時轉移到硬體的資料。