一、位圖的引入

先來看下邊一道面試題：

給40億個不重復(fù)的無符號整數(shù)，沒排過序。給一個無符號整數(shù)，如何快速判斷一個數(shù)是否在這40億個數(shù)中。

經(jīng)過我們之前的學(xué)習(xí)，我們可能會有以下的思路：

• 對這些數(shù)進行排序，再通過二分算法，查找這個數(shù)是否存在

• 插入到unordered_set中，使用find函數(shù)查找是否存在

上述方法看起來還不錯，二分查找算法時間復(fù)雜度為logN,而插入到unordered_set中時間復(fù)雜度為O(N),而查找時時間復(fù)雜度為O(1)，但是都有一個問題就是要將空間不足，40億個無符號整形，需要160億字節(jié)的空間，大概就是16GB的空間，一般計算機的內(nèi)促都是4G或者8G，所以空間不足，此時就有了位圖的方法來解決：

數(shù)據(jù)是否在給定的整形數(shù)據(jù)中，結(jié)果是在或者不在，剛好是兩種狀態(tài)，那么可以使用一個二進制比特位來代表數(shù)據(jù)是否存在的信息，如果二進制比特位為1，代表存在，為0代表不存在。比如：

對于上圖來說，有一個整形數(shù)組，我們可以使用直接定址法對數(shù)組的數(shù)據(jù)進行映射，但是與之前不同的是，此時只是使用一個比特位來代表一個整形數(shù)據(jù)，當(dāng)這個數(shù)存在時，比特位置1，不存在時，比特位置0,此時就可以大大節(jié)省空間資源，無符號整數(shù)只有2的32次方個，所以最多開2的32次方個空間，一個空間為一個比特，所以最終只需要512MB的空間。但是我們不能按照位來空間，最少必須一個字節(jié)，所以我們就每次開一個字節(jié)的空間，也就是8個比特位，將8位當(dāng)做一個整體來處理，對要保存的數(shù)據(jù)除8就是第幾個字節(jié)，對保存的數(shù)據(jù)模8就是在這個字節(jié)中的第幾個位置。

二、位圖的概念

所謂位圖，就是用每一位來存放某種狀態(tài)，適用于海量數(shù)據(jù)，數(shù)據(jù)無重復(fù)的場景。通常是用來判斷某個數(shù)據(jù)存不存在的。

那么位圖還有哪些應(yīng)用呢？

• 快速查找某個數(shù)據(jù)是否在一個集合中

• 排序 + 去重

• 求兩個集合的交集、并集等

• 操作系統(tǒng)中磁盤塊標記

位圖模擬實現(xiàn)

一、構(gòu)造函數(shù)

由于不能按位開空間，所以我們選擇每次開一個字節(jié)的空間，由于有范圍最大為N，一位關(guān)聯(lián)一個數(shù)據(jù)，所以需要開N/8個字節(jié)的空間，但是有時可能不能整除，所以要開N/8+1個字節(jié)的空間。所以

直接在構(gòu)造函數(shù)中開好空間：

bitset(){_bits.resize(N / 8 + 1,0);}

二、set，reset，test函數(shù)

set函數(shù)的作用是對位圖中的某一位進行填充

i就表示是第幾個字節(jié)，而j表示該位在該字節(jié)中的第幾位，所以對1進行左移j位后與該字節(jié)按位或，按位或的作用時不論該位為0還是為1，都將該位變?yōu)?。

void set(size_t x){int i = x / 8;int j = x % 8;_bits[i] |= (1 << j);}

reset的作用是將某一位清空

同樣的將要清空的那一位置為0，進行按位與，不論原本該位是0還是1，都將該位置0

void reset(size_t x){int i = x / 8;int j = x % 8;_bits[i] &= ~(1 << j);}

test的作用是檢測位圖中某一位是否存在

bool test(size_t x){int i = x / 8;int j = x % 8;return _bits[i] & (1 << j);}

三、代碼測試

void test_bit_set1(){bitset<100> bs1;bs1.set(8);bs1.set(9);bs1.set(20);cout << bs1.test(8) << endl;cout << bs1.test(9) << endl;cout << bs1.test(20) << endl;bs1.reset(8);bs1.reset(9);bs1.reset(20);cout << bs1.test(8) << endl;cout << bs1.test(9) << endl;cout << bs1.test(20) << endl;}

四、完整代碼

namespace tmt
{template<size_t N>class bitset{public:bitset(){_bits.resize(N / 8 + 1,0);}void set(size_t x){int i = x / 8;int j = x % 8;_bits[i] |= (1 << j);}void reset(size_t x){int i = x / 8;int j = x % 8;_bits[i] &= ~(1 << j);}bool test(size_t x){int i = x / 8;int j = x % 8;return _bits[i] & (1 << j);}private:vector<char> _bits;};void test_bit_set1(){bitset<100> bs1;bs1.set(8);bs1.set(9);bs1.set(20);cout << bs1.test(8) << endl;cout << bs1.test(9) << endl;cout << bs1.test(20) << endl;bs1.reset(8);bs1.reset(9);bs1.reset(20);cout << bs1.test(8) << endl;cout << bs1.test(9) << endl;cout << bs1.test(20) << endl;}