BitArray類用於在資源有限的情況下表示一系列比特值。比特集合可以存儲於常規數組,但是如果我們使用專為比特集合設計的數據結構則可以創建更高效的程序。在本章中,我們將學習一下怎樣使用這種數據結構並研究一些可以使用比特集合來解決的問題。本章中同時復習了二進制數字,以及按位比較與移位運算符。
一個激起興趣的問題
讓我們看一個將最終使用BitArray類來解決的問題。這個問題的要求是找到質數。一個比較原始的方法是公元前三世紀的希臘哲學家埃拉托色尼發現的被稱為愛拉托遜斯篩法的方法。這個方法過濾掉可以整除其它數字的數字,直到剩下的數字均為質數為止。例如,讓我們找出前100個整數這個集合中的質數。我們由第一個質數2開始。我們遍歷集合移除所有2的倍數。然後我們繼續下一個質數3。我們再次遍歷集合,移除所有3的倍數。接著我們移動到5,如此繼續。當我們完成時,所有剩下的數字都是質數。
首先我們使用一個常規數組解決這個問題。我們將使用的這種方法與即將使用的用一個BitArray來解決問題的方法很類似,都是初始化數組的100個元素,並將每個元素的值置為1。由索引2開始(由於2是第一個質數),每個後來的數組索引都首先被查看值為1還是0。如果值為1,接著判斷索引數是否為2的倍數。如果是,將這個索引位置的值設置為0。然後我們移動到索引3,進行相同的處理並繼續。
要編寫代碼解決這個問題,我們將使用之前編寫的Carray類。首先要做的是創建一個方法來執行篩選。如下是代碼:
public void GenPrimes()
{
int temp;
for (int outer = 2; outer <= arr.GetUpperBound(0); outer++)
for (int inner = outer + 1; inner <= GetUpperBound(0); inner++)
if (arr[inner] == 1)
if ((inner % outer) == 0)
arr[inner] = 0;
}
現在我們僅需要就是一個顯示質數的方法:
public void ShowPrimes()
{
for (int i = 2; i <= arr.GetUpperBound(0); i++)
if (arr[i] == 1)
Console.Write(i + " ");
}
下面是一個測試我們代碼的程序:
static void Main()
{
int size = 100;
CArray primes = new CArray(size - 1);
for (int i = 0; i <= size - 1; i++)
primes.Insert(1);
primes.GenPrimes();
primes.ShowPrimes();
}
這個方法展示了怎樣在整數數組中使用愛拉托遜斯篩法,但是更好的建議是使用比特來開發一個解決方案,因為這種數組中每個元素都是1或0。本章後面我們將學習怎樣使用BitArray類來同時實現愛拉托遜斯篩法與其他將自己借位給比特集合的問題。
位與位操作
在我們研究BitArray類之前,我們需要研究怎樣在VB.NET中使用位,由於在位一級操作是大多數VB.NET程序員所不熟悉的。在本節中,我們將學習怎樣在VB.NET中操作位,主要通過學習怎樣使用按位運算符操作比特值來學習。
二進制計數系統
在學習操作比特值之前,讓我們復習一下二進制計數系統。二進制數字是使用0與1兩個字符串來將基於10的(十進制)數字以基於2的數字來表示。例如,二進制中整數0表示如下:
00000000
整數1的二進制數字為:
00000001
如下是二進制中整數0-9所顯示的形式:
00000000—0d (where d signifies a decimal number)
00000001—1d
00000010—2d
00000011—3d
00000100—4d
00000101—5d
00000110—6d
00000111—7d
00001000—8d
00001001—9d
最佳的將一個二進制數字轉換為等值的十進制的方法是使用如下的方案。每一個二進制數字中,由最右端數字開始都代表了一個連續增大的2的冪。如果第一個位置上的數字是一個1,則其代表20。如果第二個位置有一個1,則其代表21,等等。
二進制數字:
00101010
等價於:
0 + 21 + 0 + 23 + 0 + 25 + 0 + 0 = 0 + 2 + 0 + 8 + 0 + 32 + 0 + 0 = 42
位通常顯示於8個位的集合中,這組成了一個字節。使用8個位可以表示的最大數字為255,二進制如下:
11111111
或
1 + 2 + 4 + 8 + 16 + 32 + 64 + 128 = 255
一個大於255的數字必須存儲於16位中。例如二進制數表示的256為:
00000001 00000000
雖然不是必須,但習慣上將低8位與高8位分隔。
操作二進制數字:按位操作與位移操作符
二進制數字並不使用基本算術運算符來操作。你必須使用按位操作運算符(And, Or, Not)或位移操作運算符(<<, >>, and >>>)。在這節中,我們解釋這些運算符怎樣工作並在後面的章節演示它們在VB.NET程序中的使用。
首先,我們研究按位操作運算符。這些大多數程序員已經熟悉的邏輯運算符 – 它們用來合並相關的表達式以便計算一個單一的布爾值。按位運算符操作二進制數字,逐位比較兩個二進制數字,迭代生成一個新的二進制數字。
按位運算符以操作布爾值相同的方式工作。當操作二進制數字時,True位等價於1,False位等價於0。我們使用一個真值表來展示按位運算符對位的操作,正如對布爾值操作使用的真值表那樣。一行中前兩列為操作數,第三列為運算結果。And操作的真值表(布爾值表示)如下:
True
True
True
True
False
False
False
True
False
False
False
False
等價的位值的真值表:
1
1
1
1
0
0
0
1
0
0
0
0
Or操作的布爾值真值表為:
True
True
True
True
False
True
False
True
True
False
False
False
等價的位值的真值表:
1
1
1
1
0
1
0
1
1
0
0
0
最後是Xor運算符。這是最不被了解的一個按位運算符,因為其不用於計算機程序執行的邏輯運算。當兩個位值進行Xor比較操作時,當兩個位操作數中恰有一個為1時結果為1,如下是真值表:
1
1
0
1
0
1
0
1
1