位图：Bitmapdosdiosas的博客-

援引自维基百科：

     A bit array (also known as bit map, bit set, bit string, or bit vector) is an array data structure that compactly stores bits. It can be used to implement a simple set data structure. A bit array is effective at exploiting bit-level parallelism in hardware to perform operations quickly. A typical bit array stores kw bits, where w is the number of bits in the unit of storage, such as a byte or word, and k is some nonnegative integer. If w does not divide the number of bits to be stored, some space is wasted due to internal fragmentation.

下面给出位图的实现：

#pragma warning(disable:4996) #include<iostream> #include<algorithm> #include<memory> using namespace std; //位图：Bitmap类 class Bitmap { private: char* M;//比特图所存放的空间M[]，容量为N*sizeof(char)*8比特 int N; protected: void init(int n) {   N = (n + 7) / 8;   M = new char[N]; memset(M, 0, N); } public: Bitmap(int n = 8) { init(n);//按指定或默认规模创建比特图 } Bitmap(char* file, int n = 8) { //按指定规模或者默认规模，从文件之中读取比特图 init(n);   FILE* fp = fopen(file, "r"); fread(M, sizeof(char), N, fp); fclose(fp); } ~Bitmap() { delete[]M;   M = NULL;//析构时释放比特图空间 } void set(int k) { expand(k);   M[k >> 3] |= (0x80 >> (k & 0x07)); } void clear(int k) { expand(k);   M[k >> 3] &= ~(0x80 >> (k & 0x07)); } bool test(int k) { expand(k); return M[k >> 3] & ((0x80) >> (k&0x07)); } void dump(char* file) { //将位图整体导出至指定文件，以便此后对新的位图进行整体初始化   FILE* fp = fopen(file, "w"); fwrite(M, sizeof(char), N, fp); fclose(fp); } char* bits2string(int n) { //将前N位转换为字符串 expand(n - 1);//此时可能被访问的最高位为bitmap[n-1] char* s = new char[n + 1];   s[n] = ''; for (int i = 0; i < n; i++) {    s[i] = test(i) ? '1' : '0'; } return s;//返回字符串 } void expand(int k)//若被访问的Bitmap[k]已出界，则需扩容 { if (k < 8 * N) { return;//若仍在界内，无需扩容 } int oldN = N; char* oldM = M; init(2 * k);//与向量类似，加倍策略 memcpy_s(M, N, oldM, oldN); //将元数据转移至新的的空间 delete[] oldM; } }; int main() { int n = 1000;  Bitmap bt(n); for (int i = 0; i< n; i++) {   bt.set(i); } if (bt.test(20000)) {   cout << "founded!" << endl; } else {   cout << "not founded!" << endl; } system("pause"); return 0; } 

在上述实现过程中使用了位运算，这里的是现实充分考量了计算机做数据存储的特点，以及位图数据结构的优势。请大家仔细思考。

大致解释如下：

①：如何由一个整数k定位到指定位置？

思路是先定位到第k比特所在的字节位置，然后在计算出它所在这个字节的第几位。因为一个字节（char）占8位，所以可以由 k >> 3 算出第k比特所在字节位置，这里设找到的这个字节位 b。然后计算它所在8位字节 b 的第几位，用 k % 8 即可得到，写成位运算 k & 0x07 ，获得低三位所等价的数字，这里设为 x。

②

定位到了指定位，如何修改它？

已经找到了第k比特在字节 b 的 第 x 位。如果要将k添加进位图，就需要将字节 b 的 第 x 位设置为1，只需用一个第 x 位为1的字节与字节 b 做或运算即可。构造这样的字节：0b 1000 0000 >> x（就是：0x80 >> (k & 0x07)），就可以将字节第 x 为设为1。然后通过位运算 | ，M[k >> 3] |= (0x80 >> (k & 0x07))。