BitMap
位圖（bitmap）是一種非常常用的結構，在索引，數據壓縮等方面有廣泛應用。位圖是通過將數組下標與應用中的一些值關聯映射，數組中該下標所指定的位置上的元素可以用來標識應用中值的情況（是否存在或者數目 或者計數等），位圖數組中每個元素在內存中占用1位，所以可以節省存儲空間。位圖是一種非常簡潔快速的數據結構，它能同時使存儲空間和速度最優化。如可用一個10位長的字符串來表示一個所有元素都小于10的簡單的非負整數集合，例如，可以用如下字符串表示集合{1,2,4,5,8} ，對應位置數字存在標記為1，否則標記為0。
這里BitMap指的是把數據存放在一個以bit為單位的數據結構里。
每位都只有0和1兩個值。為0的時候，證明值不存在，為1的時候說明存在。
舉例來說：
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
這是24位，也就是24bit, 同時8bit為1個字節。這里的空間也就是3個字節。
這個時候假如我們要存放2 4 6 8 9 10 17 19 21這些數字到我們的BitMap里，我們只需把對應的位設置為1就可以了。
[0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 1 1 0 1 0 1 0 1 0]
數據結構
假如，我們要存儲的數據范圍為0-15，這里的數據是16bit:
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
數據為[5, 1, 7, 15, 0, 4, 6, 10]
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
[1 0 0 0 0 1 0 0 1 1 1 1 0 0 1 1]
例如：
申請一個int型的內存空間，則有4Byte，32bit。輸入 4， 2, 1, 3時：
輸入4：
[ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0]
輸入2：
[ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0]
輸入1：
[ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0]
輸入3：
[ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0]
map映射表
假設需要排序或者查找的總數N=10000000,那么我們需要申請的內存空間為 int a[N/32 + 1].其中a[0]在內存中占32位,依此類推：
bitmap表為：
a[0] ——> 0 - 31
a[1] ——> 32 - 63
a[2] ——> 64 - 95
a[3] ——> 96 - 127
……
位移轉換
求十進制數0-N對應的在數組a中的下標
公式：index = N / 32即可，index即為對應的數組下標。例如N = 76, 則index = 76 / 32 = 2,因此76在a[2]中。求十進制數0-N對應的bit位
bit = N % 32即可，例如 N = 76, bit = 76 % 32 = 12利用移位0-31使得對應的32bit位為1
代碼實現
##include <iostream>
#include <vector>using namespace std;class BitMap
{
public:BitMap( int range ){//開辟空間this->m_bits.resize(range / 32 + 1);}void set( int data ){int index = data / 32; //數組索引即區間int temp = data % 32; //具體位置索引this->m_bits[index] |= ( 1 << temp); //左移4位置為1}void reset( int data){int index = data / 32;int temp = data % 32;this->m_bits[index] &= ~( 1 << temp ); //取反}bool test(int data){int index = data / 32;int temp = data % 32;if( this->m_bits[index]&( 1 << temp)){return true;}else{return false;}}private:vector<int> m_bits;
};void testBitMap()
{BitMap bitmap_1(-1);BitMap bitmap_2(31);bitmap_2.set(16);bitmap_2.set(1);cout<< bitmap_2.test(16) << endl;bitmap_2.reset(16);cout<< bitmap_2.test(16) << endl;
}int main()
{testBitMap();
}
