位图法介绍

一、定义
位图法就是bitmap的缩写。所谓bitmap，就是用每一位来存放某种状态，适用于大规模数据，但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的。在STL中有一个bitset容器，其实就是位图法，引用bitset介绍：

A bitset is a special container class that is designed to store bits (elements with only two possible values: 0 or 1,true or false, ...).The class is very similar to a regular array, but optimizing for space allocation: each element occupies only one bit (which is eight times less than the smallest elemental type in C++: char).Each element (each bit) can be accessed individually: for example, for a given bitset named mybitset, the expression mybitset[3] accesses its fourth bit, just like a regular array accesses its elements.

数据结构

unsigned int bit[N];

在这个数组里面，可以存储 N*sizeof(int)*8个数据，但是最大的数只能是
N*sizeof(int)*8-1。

相关操作

写入数据

定义一个数组： unsigned char bit[8*1024];这样做，能存 8K*8=64K 个 unsigned short 数据。bit 存放的字节位置和位位置（字节0~8191,位 0~7 ）比如写1234，字节序：1234/8 = 154; 位序： 1234 &0b111 = 2 ，那么 1234 放在 bit 的下标 154 字节处，把该字节的 2 号位（ 0~7）置为 1。

字节位置： int nBytePos =1234/8 = 154;
位位置：   int nBitPos = 1234 & 7 = 2;

比如写入 1236 ，
字节位置： int nBytePos =1236/8 = 154;
位位置：   int nBitPos = 1236 & 7 = 4

// / 把数组的 154 字节的 4 位置为 1  
val = 1<<nBitPos;  
arrBit[nBytePos] = arrBit[nBytePos] |val;  // 再写入 1236 得到arrBit[154]=0b00010100  

代码实现

#define SHIFT 5    
#define MAXLINE 32    
#define MASK 0x1F    
void setbit(int *bitmap, int i){    
    bitmap[i >> SHIFT] |= (1 << (i & MASK));    
}  

读指定位

bool getbit(int *bitmap1, int i){    
   return bitmap1[i >> SHIFT] & (1 << (i & MASK));    
}   

位图法的应用

• 使用位图法判断整形数组是否存在重复遍历数组，一个一个放入bitmap，并且检查其是否在bitmap中出现过，如果没出现放入，否则即为重复的元素。