Bitmap¶

也就是用 1 个 (或几个)bit 位来标记某个元素对应的 value(如果是 1bitmap，就只能是元素是否存在; 如果是 x-bitmap,还可以是元素出现的次数等信息)。使用 bit 位来存储信息，在需要的存储空间方面可以大大节省。应用场景有：

判断某个元素是否存在
排序（如果是 1-bitmap,就只能对无重复的数排序）

比如，某文件中有若干 8 位数字的电话号码，要求统计一共有多少个不同的电话号码？

分析：8 位最多 99 999 999, 如果 1Byte 表示 1 个号码是否存在，需要 95MB 空间，但是如果 1bit 表示 1 个号码是否存在，则只需要 95/8=12MB 的空间。这时，数字 k(0~99 999 999) 与 bit 位的对应关系是：

#define SIZE 15*1024*1024
char a[SIZE];
memset(a,0,SIZE);

// a[k/8]这个字节中的 `k%8` 位命中,置为1
// 这里要注意 big-endian 和  little-endian的问题 ，假设这里是big-endian
a[k/8] = a[k/8] | (0x01 << (k%8))