什么是Bitmap
Bitmap，也叫做bit array，顾名思义，是一种以bit为单位进行信息存储的数组。但Bitmap存储的“信息”又有些特殊，这是因为一个bit只能有两种取值0、1，所以bitmap通常用来存储这种能编码为0、1的状态信息：absent/present，dark/light，invalid/valid等。
我们就拿absent/present来举例，如果某个bit的值是1，那就表示该bit是存在的。所以我们完全可以把Bitmap当成“集合”（准确地说是带hash功能的set）去使用：集合中的元素就由bit数组中所有值为1的元素所在的位置组成。反过来看，Bitmap就是把某些元素（通常是整数）转化为为0、1的一种映射。
Bitmap的诞生是为了解决什么问题
Bitmap最大的优势就是采用了bit为单位存储信息，极大地节约了存储空间。举个例子来说，如果我们要存储[4,2,1,3]四个整数，在c++中，我们通常会这样做：int[] arr = {4, 3, 2, 1};。这样的做法会产生一个占用4 * 4 = 16个字节的数组arr。
但如果我们用Bitmap呢？比如给定一个长度是10bit的内存空间，我们现在插入4,2,1,3。我们可以将长度为10的bitmap的每一个bit位分别对应着0到9这10个整数。一开始bitmap所有位都是0（对应着图中的蓝色），之后每插入一个整数，该整数对应的存储位置的bit置为1（对应图中的红色）。
这样，我们可以用10bit的内存空间去表示{4, 3, 2, 1}四个整数，相比起之前的20个字节，极大地节省了存储空间。如果整数个数更多，空间节省也就越明显。
如何实现一个简单的Bitmap
我们可以用整型数组表示bit数组。如果一个整数32位，那么表示N个连续的整数，bit数组的长度只需要N/32。bitmap通常有三种操作：set（置位），clear（清位），get（读位）。
// http://blog.csdn.net/QIBAOYUAN/article/details/5914662
#define WORD 32
#define SHIFT 5 ////移动5个位,左移则相当于乘以32,右移相当于除以32取整
#define MASK 0x1F //16进制下的31
#define N 10000000
int bitmap[1 + N / WORD];
/*
* 置位函数——用"|"操作符,i&MASK相当于mod操作
* m mod n 运算，当n = 2的X次幂的时候,m mod n = m&(n-1)
*/
void set(int i) {
bitmap[i >> SHIFT] |= (1 << (i & MASK));
}
/* 清除位操作，用&~操作符 */
void clear(int i) {
bitmap[i >> SHIFT] &= ~(1 << (i & MASK));
}
/* 测试位操作用&操作符 */
int get(int i) {
return bitmap[i >> SHIFT] & (1 << (i & MASK));
}
Bitmap存在的问题
同样的空间大小，bit数组存储的元素个数虽然比整型数组多，但是由于bit数组能存储的元素最大值一般等于bit数组元素个数。所以，如果面对稀疏的整数存储任务，bit数组会开辟出很大的存储空间，而且会造成严重的空间碎片。
但这也不是问题，通过引入RLW：Running Length Word，可以避免空间的浪费。具体可以阅读Bitmap算法（进阶篇）。
Bitmap的常见应用
- 给40亿个不重复的unsigned int整数，未排序，然后再给一个数，如何快速判断这个数是否在40亿个数中？
如果40亿个数直接放在内存中，需要大约16GB内存，用bitmap不超过512MB。
- 在2.5亿个整数中找出不重复的整数。注：内存不足以容纳2.5亿个整数
不重复包含了三种状态：00表示不存在，01表示出现一次，10表示多次，11无意义。所以和之前不同，这里我们需要给每个整数分配2个bit，也就是用2-Bitmap去实现。
#define WORD 16
#define SHIFT 4 ////移动4个位,左移则相当于乘以16,右移相当于除以16取整
#define MASK 0xF //16进制下的15
#define MAX_N 10000000
/*
* 置位函数——用"|"操作符,i&MASK相当于mod操作
* m mod n 运算，当n = 2的X次幂的时候,m mod n = m&(n-1)
*/
void bitmap_set(int i, int* bitmap, unsigned int count) {
int j = i & MASK;
// unsigned int t = (bitmap[i >> SHIFT] & ~((0x3 << (2 * j))&0xffffffff)) | (((count % 4) << (2 * j)) & 0xffffffff);
unsigned int t = (bitmap[i >> SHIFT] & ~(0x3 << (2 * j))) | ((count % 4) << (2 * j));
bitmap[i >> SHIFT] = t;
}
int bitmap_get(int i, int* bitmap) {
int j = i & MASK;
// 0x3 十六进制表示00 00 00 11
unsigned int count = (bitmap[i >> SHIFT] & (0x3 << (2 * j))) >> (2 * j);
return count;
}
void add_count(int i, int* bitmap) {
unsigned int count = bitmap_get(i, bitmap);
if (count >= 2) return;
bitmap_set(i, bitmap, count+1);
}
int main() {
int* bitmap = NULL;
freopen("in.txt", "r", stdin);
bitmap = (int*)malloc(sizeof(int)*(1+MAX_N/WORD));
memset(bitmap, 0, sizeof(int)*(1+MAX_N/WORD));
int num;
while (scanf("%d", &num) != EOF) add_count(num, bitmap);
for (int i = 0; i < 1000000; i++) {
if (bitmap_get(i, bitmap) == 1) printf("%d\n", i);
}
return 0;
}
如果考虑负整数的话，再单独开辟出一个2-Bitmap为负整数服务就可以。