一、定义
位图法就是bitmap的缩写。所谓bitmap，就是用每一位来存放某种状态，适用于大规模数据，但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的。在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.
数据结构
unsigned int bit[N];
在这个数组里面，可以存储 N*sizeof(int)*8个数据，但是最大的数只能是
N*sizeof(int)*8-1。
相关操作
写入数据
定义一个数组： unsigned char bit[8*1024];这样做，能存 8K*8=64K 个 unsigned short 数据。bit 存放的字节位置和位位置（字节0~8191,位 0~7 ）比如写1234，字节序：1234/8 = 154; 位序： 1234 &0b111 = 2 ，那么 1234 放在 bit 的下标 154 字节处，把该字节的 2 号位（ 0~7）置为 1。
字节位置： int nBytePos =1234/8 = 154;
位位置： int nBitPos = 1234 & 7 = 2;
比如写入 1236 ，
字节位置： int nBytePos =1236/8 = 154;
位位置： int nBitPos = 1236 & 7 = 4
// / 把数组的 154 字节的 4 位置为 1
val = 1<<nBitPos;
arrBit[nBytePos] = arrBit[nBytePos] |val; // 再写入 1236 得到arrBit[154]=0b00010100
代码实现
#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));
}
位图法的应用
- 使用位图法判断整形数组是否存在重复遍历数组，一个一个放入bitmap，并且检查其是否在bitmap中出现过，如果没出现放入，否则即为重复的元素。
