bitmap是一种简单的数据结构。但在存储空间压缩方面却使用广泛。
bitmap就是用一个bit位来标记某个元素是否存在：1表示存在，0表示不存在；而2-bitmap就是用两个bit为来标记某个元素出现的次数：00出现0次，01出现1次。10出现2次及其以上。11无意义。
2-bitmap在内存中的表演示样例如以下：
[0] [1] [2] ……
|00 00 00 00|00 00 00 00|00 00 00 00| ……
3 2 1 0 7 6 5 4 11 10 9 8 ……
不论什么一个可採用数组作为辅助标记来解决的问题都能够用bitmap来解决，由于用数组的每一个元素作为标记的话，用bit相同能够作为标记。当数据量比較小时，有时候为了操作方便，可直接採用数组。但当数据量非常大的时候，由于内存大小的原因或题目限定了可用内存大小，数组就再没法解决我们的问题。 而此时bitmap就显示出其空间压缩的威力了：假设用char型的数组，标记相同范围内的数bitmap最多能够节省8倍空间，2-bitmap可节省4倍空间。若採用int型的数组。bitmap和2-bitmap能够分别最多节省32倍、16倍的空间。
bitmap能用来处理以下问题：
（1）、字符串方面
1、C语言str系列库函数之strtok()、strspn()、strcspn()和strpbrk()函数都用到了bitmap。
详见C语言str系列库函数之strtok()、C语言str系列库函数之strspn()、strcspn()和strpbrk()；
2、推断一个字符串B中的字符是否都在还有一个字符串A中出现（网上能搜到）。
跟上面第1条博文链接里的十分相似。
3、在一个字符串中找到第一个仅仅出现一次的字符（google面试题、网上能搜到）。
能够用26维的数组统计26个字母出现的次数。然后顺序查找统计表直到查到到结果为1的就是要查到的字符。
也能够採用2-bitmap，更节省空间。
（2）、大数据
1、在2.5亿个整数找出不反复的整数，内存不足以容纳着2.5亿个整数
2、腾讯面试题：给40亿个不反复的unsigned int的整数。没排过序的，然后再给一个数，怎样高速推断这个数是否在那40亿个数其中？
对于问题1。整数可能是正数也可能是负数，首先仅仅考虑正整数情况，採用2Bitmap方法，用00表示不存在，01表示出现1次，10表示出现2次及以上，此方法总共须要的内存2^31*2bit = 1Gb = 128MB（32位的正整数有2^31个，每一个存储须要2bit，所以就是1Gb，换成字节就是128MB），这样内存就应该能够容纳了，最后在处理全然部的数后，仅仅要输出相应位为01的数就可以。
假设这2.5亿个数里面既有正数又有负数那么就用两个2Bitmap分别存储正数和负数（取绝对值存储），零就随便放。这是所须要的内存是256MB。
对于问题2，直接用Bitmap就可以，0表示存在，1表示不存在。
很多其它关于用bitmap来解决这个问题的博文：十七道海量数据处理面试题与Bit-map具体解释、http://blog.csdn.net/v_july_v/article/details/7382693
2-bitmap的使用关键在于怎样操纵位，以下是一个演示样例代码：
#include <stdio.h>
#include <memory.h>
#include <stdlib.h>
#define N 1024*1024*1024
unsigned char bitmap[1 + N / 4]; //2-bitmap
void set(int x,int num)
{
int m = x >> 2; //x / 4;
int n = x & 0x3; //x % 4;
//bitmap[m] &= ~((0x3<<(2*n)) & 0xff);
//bitmap[m] |= ((num&0x3)<<(2*n) & 0xff);
bitmap[m] &= ~(0x3 << (2*n));
bitmap[m] |= ((num & 0x3) << (2*n));
}
void clear(int x)
{
int m = x >> 2; //x / 4;
int n = x & 0x3; //x % 4;
//bitmap[m] &= ~((0x3<<(2*n)) & 0xff); //0xff能够去掉
bitmap[m] &= ~(0x3 << (2*n));
}
unsigned get(int x)
{
int m = x >> 2;
int n = x & 0x3;
return (bitmap[m] & (0x3 << (2*n))) >> (2*n);
}
void add(int x)
{
set(x, get(x) + 1);
}
int main()
{
int a[8] = {1, 3, 1, 4, 5, 5, 5, 5}; //找出数组a中不反复的元素
memset(bitmap, 0, sizeof(bitmap)); //清空位图
for (int i = 0;i < 8; i++)
{
unsigned val = get(a[i]); //00、01、10
if (val <= 1) //a[i]在bitmap的位序列为10时表示出现最少2次
set(a[i], val+1);
}
//如今能够查看每一个元素出现的次数
for (int i = 0;i < 8; i++)
printf("%d %d
", a[i], get(a[i]));
putchar('
');
//假设要推断某个数x是否存在于数组a中,直接推断get(x)的值
//get(x) > 0 ？ 存在 ： 不存在
//以下的代码输出在a数组中仅出现1次的数
for (int i = 0; i < 2;i++) //这里实际上仅仅须要用到16bit
for(int j = 0; j < 4; j++)
{
int x = (i << 2 | (j & 0x3)); //得到存在这个位置的数是多大
int val = get(x);
if (val == 1)
printf("%d ", x);
}
getchar();
return 0;
}參考：http://blog.csdn.net/acceptedxukai/article/details/9025493