1. 简述
位图文件（bitmap）是一种十分常见的构造，在数据库索引，数据编码等层面有广泛运用。文中详细介绍了位图文件的完成方式以及应用领域。
2. 位图文件完成
（1）自身完成
当政图上，每一个原素为“0”或“1”，表明其相匹配的原素不会有或是存有。
#define INT_BITS sizeof(int)
#define SHIFT 5 // 2^5=32
#define MASK 0x1f // 2^5=32
#define MAX 1024*1024*1024 //max number
int bitmap[MAX / INT_BITS];
/*
* 设定第i位
* i >> SHIFT 等同于 i / (2 ^ SHIFT),
* i&MASK等同于mod实际操作 m mod n 计算
*/
void set(int i) {
bitmap[i >> SHIFT] |= 1 << (i & MASK);
}
//获得第i位
int test(int i) {
return bitmap[i >> SHIFT] & (1 << (i & MASK));
}
//消除第i位
int clear(int i) {
return bitmap[i >> SHIFT] & ~(1 << (i & MASK));
}
（2）库函数完成
C 的STL中有bitmap类，它出示了许多 方式，详细：http://www.cplusplus.com/reference/stl/bitset/
3. 位图文件运用
3.1 枚举类型
（1）全组成
字符串数组全组成枚举类型（针对长短为n的字符串数组，组成方法有2^n种），如：abcdef,能够结构一个从字符串数组到二进制的投射关联，根据枚举类型二进制来开展全排列。
null——> 000000
f——> 000001
e——> 000010
ef——> 000011
……
abcedf——> 111111
（2）哈米尔顿间距
枚举算法，复杂性是O(N^2)，如何减少复杂性呢？
如果是N 个二维的点，那麼我们可以如何使用迅速的方式求出
根据简易的数学课形变，我们可以获得那样的公式：
仔细观察，大家发觉每一对同样元的符号必然反过来，如：x_i-y_i，因此大家拥有一个二进制观念的构思，那便是枚举类型这种二i维的点的x 轴y 轴前的绝对值符号，那样就可以用一个0~3 的数的二进制方式来表明每一个原素前边的绝对值符号，1表明 号，0表明−号，如：2 表明的二进制位方式为10表明x_i-y_i。那样大家就可以根据2^2*N次纪录下这种二元组的不一样的标记的标值，针对每一个二进制来表明的不一样的算式只需纪录下她们的值，那样大家只要求max_i 和min_i出这种同样的二进制表明的算式max_i –min_i，最终大家就可以解出ans=max{max_i-min_i}。
根据位图文件，优化算法算法复杂度可将为O(N)。
3.2 检索
设计方案检索修枝时，必须储存早已检索过的历史时间信息内容，有一些状况下，能够应用位图文件减少历史时间信息内容数据信息所占室内空间。
3.3 缩小
（1） 在2.五亿个整数金额中找到不反复的整数金额，注，内存不够以容下这2.五亿个整数金额？
（2） 腾讯面试题：给40亿次不反复的unsigned int的整数金额，未排过序的，随后再给一个数，怎么才能分辨这一数是不是在哪40亿数量之中？
4. 小结
Bitmap是一种十分简约迅速的算法设计，他能同使证储存空间和速率最优控制（而无须室内空间换時间）。
5. 参考文献
（1） 《C实现bitmap位图》：
http://blog.csdn.net/QIBAOYUAN/archive/2010/09/29/5914662.aspx
（2） 武森《浅谈信息学竞赛中的“0”和“1”》
