昨晚遇到了一种很有意思的数据结构，Bitmap。
Bitmap，准确来说是基于位的映射。其中每个元素均为布尔型（0 or 1），初始均为 false(0)。位图可以动态地表示由一组无符号整数构成的集合。 每个bit对应一个无符号数。如位图第10个比特为true(1)，表示无符号整数9。
之所以用位图来表示整数，是为了 节省 内存。假如要处理50亿个四字节无符号整数，那么需要 5,000,000,000 * 4bytes = 20,000,000,000bytes = (20,000,000,000 / 1024 / 1024 / 1024)GB = 18.63GB 内存，显然普通的计算机无法处理。如果使用位图的话，每个位映射为一个数，则只需要 1bit * 5,000,000,000 = (5,000,000,000 / 8)bytes = (625,000,000 / 1024 / 1024)MB = 596MB，需要的内存降到了 1/32。
如何由一个整数k定位到指定位置？
思路是先定位到第k比特所在的字节位置，然后在计算出它所在这个字节的第几位。
因为一个字节（char）占8位，所以可以由 k >> 3 算出第k比特所在字节位置，这里设找到的这个字节位 b。
然后计算它所在8位字节 b 的第几位，用 k % 8 即可得到，写成位运算 k & 0x07 ，获得低三位所等价的数字，这里设为 x。
定位到了指定位，如何修改它？
已经找到了第k比特在字节 b 的 第 x 位。如果要将k添加进位图，就需要将字节 b 的 第 x 位设置为1，只需用一个第 x 位为1的字节与字节 b 做或运算即可。构造这样的字节：0b1000_0000 >> x（就是：0x80 >> (k & 0x07)），就可以将字节第 x 为设为1。然后通过位运算 | ，M[k >> 3] |= (0x80 >> (k & 0x07))。
完整的 Bitmap C++代码：
//代码来自邓俊辉数据结构习题集
class Bitmap {
private:
char *M; //比特图所存放的空间为M[]
int N; //容量为 N*sizeof(char)*8，就是N*8，一个字节8位
protected:
void init(int n) {
M = new char[N = (n + 7) / 8];
memset(M, 0, N); //将指针M后的N个字节用0代替，初始化位图，位全设置为0
}
public:
Bitmap(int n = 8) { //按指定规模创建比特图
init(n);
}
Bitmap(char* file, int n = 8) { //从文件中读取比特图
init(n);
FILE* fp = fopen(file, "r");
fread(M, sizeof(char), N, fp);
fclose(fp);
}
~Bitmap() { //释放比特图空间
delete[] M;
M = nullptr;
}
void set(int k) { //设置第k个比特为1
expand(k);
M[k >> 3] |= (0x80 >> (k & 0x07));
/*
* 因为每个字节包含8个比特，所以通过位运算 k>>3 可以确定对应的比特所属第几个字节。
* 通过逻辑位与运算 k & 0x07[0b0111] 可以确定比特位所属字节的第几个位。获得k的低3比特，即比特在字节中的位置，设为x。
* 通过移位操作 0x80[128:0b1000_0000] >> (k & 0x07) 可以得到该比特位所在字节中对应的数值的掩码。
* 将(128:0b1000_0000)中最高位的1右移x。即将x位设置为1。然后 |=，将M第k字节的第x为设为1。
*/
}
void clear(int k) { //第k个比特清零
expand(k);
M[k >> 3] &= ~0x80 >> (k & 0x07);
/*
* ~0x08 是 0b01111111，将最高位0右移到第x位，然后 &= 就是设M第k个字节的第x位为0.
*/
}
bool test(int k) { //判断是否存在k
expand(k);
return M[k >> 3] & (0x80 >> (k & 0x07));
/*
* 判断M第k个字节的第x位是否为1
*/
}
void dump(char* file) {
FILE* fp = fopen(file, "w");
fwrite(M, sizeof(char), N, fp);
fclose(fp);
}
char* bits2string(int n) { //将前n位转换为字符串
expand(n - 1); //此时可能被访问的最高位为Bitmap[n-1]
char* s = new char[n + 1];
s[n] = '\0';
for (int i = 0; i < n; i++)
s[i] = test(i) ? '1' : '0';
return s;
}
void expand(int k) { //若被访问的Bitmap[k]已出，则需扩容
if (k < 8 * N) //无需扩容
return;
int oldN = N;
char* oldM = M;
init(2 * k); //加倍扩容
memcpy_s(M, N, oldM, oldN); //原数据转移至新空间
delete[] oldM;
}
};
应用：
可进行数据的快速查找，判重，删除。直接将整数k做位运算即可，复杂度为O(1)。