一祭玉、定義
位圖法就是bitmap的縮寫。所謂bitmap春畔，就是用每一位來存放某種狀態(tài)脱货，適用于大規(guī)模數(shù)據(jù)，但數(shù)據(jù)狀態(tài)又不是很多的情況律姨。通常是用來判斷某個數(shù)據(jù)存不存在的振峻。在STL中有一個bitset容器，其實就是位圖法择份，引用bitset介紹：
A bitset is a special container class that is designed to store bits (elements with only two possible values: 0 or 1,true or false, ...).The class is very similar to a regular array, but optimizing for space allocation: each element occupies only one bit (which is eight times less than the smallest elemental type in C++: char).Each element (each bit) can be accessed individually: for example, for a given bitset named mybitset, the expression mybitset[3] accesses its fourth bit, just like a regular array accesses its elements.
數(shù)據(jù)結(jié)構(gòu)
unsigned int bit[N];
在這個數(shù)組里面扣孟，可以存儲 N*sizeof(int)*8個數(shù)據(jù)，但是最大的數(shù)只能是
N*sizeof(int)*8-1荣赶。
相關(guān)操作
寫入數(shù)據(jù)
定義一個數(shù)組： unsigned char bit[8*1024];這樣做哈打，能存 8K*8=64K 個 unsigned short 數(shù)據(jù)。bit 存放的字節(jié)位置和位位置（字節(jié)0~8191,位 0~7 ）比如寫1234讯壶，字節(jié)序：1234/8 = 154; 位序： 1234 &0b111 = 2 料仗，那么 1234 放在 bit 的下標(biāo) 154 字節(jié)處，把該字節(jié)的 2 號位（ 0~7）置為 1伏蚊。
字節(jié)位置： int nBytePos =1234/8 = 154;
位位置： int nBitPos = 1234 & 7 = 2;
比如寫入 1236 立轧，
字節(jié)位置： int nBytePos =1236/8 = 154;
位位置： int nBitPos = 1236 & 7 = 4
// / 把數(shù)組的 154 字節(jié)的 4 位置為 1
val = 1<<nBitPos;
arrBit[nBytePos] = arrBit[nBytePos] |val; // 再寫入 1236 得到arrBit[154]=0b00010100
代碼實現(xiàn)
#define SHIFT 5
#define MAXLINE 32
#define MASK 0x1F
void setbit(int *bitmap, int i){
bitmap[i >> SHIFT] |= (1 << (i & MASK));
}
讀指定位
bool getbit(int *bitmap1, int i){
return bitmap1[i >> SHIFT] & (1 << (i & MASK));
}
位圖法的應(yīng)用
- 使用位圖法判斷整形數(shù)組是否存在重復(fù)遍歷數(shù)組，一個一個放入bitmap躏吊，并且檢查其是否在bitmap中出現(xiàn)過氛改，如果沒出現(xiàn)放入，否則即為重復(fù)的元素比伏。
