bitmap

位图法，用每个bit位存储状态（如0/1），用于判断某个数据是否存在。适用于数据量很大，但状态不多的情况。

STL中的bitset就是位图法。

（1）bitmap原理及实现

#pragma warning(disable : 4996 4800)
#include <stdlib.h>
#include <stdio.h>
#include <memory.h>
#include "math.h"
class Bitmap { //位图bitmap类
private:
	char* M; int N; //比特图所存放的空间M[]，容量为N*sizeof(char)*8比特
protected:
	void init(int n)   //初始化位图空间
	{
		M = new char[N = (n + 7) / 8];   //申请内存
		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; 
    } 

    //置位第k个标志位
	void set(int k)   
	{
		expand(k);   //拓容        
		M[k >> 3] |= (0x80 >> (k & 0x07));  //M[第k个标志位所在的字节(k/8 取整)] |= （第k个标志位在所在字节中的位数(取余)） 
	}

    //复位第k个标志位
	void clear(int k) 
    {
		expand(k);    //拓容 
		M[k >> 3] &= ~(0x80 >> (k & 0x07)); //M[第k个标志位所在的字节(k/8 取整)] &= ~（第k个标志位在所在字节中的位数(取余)）
	}

    //取出指定字节中的指定位
	bool test(int k) 
    {
		expand(k);    //拓容 
		return M[k >> 3] & (0x80 >> (k & 0x07));  //M[第k个标志位所在的字节(k/8 取整)] &（第k个标志位在所在字节中的位的值）
	}

    //将位图整体导出至指定的文件，以便对此后的新位图批量初始化
	void dump(char* file) 
	{
		FILE* fp = fopen(file, "w"); fwrite(M, sizeof(char), N, fp); fclose(fp);
	}

    //将前n位转换为字符串
	char* bits2string(int n)
	{ 
		expand(n - 1); //此时可能被访问的最高位为bitmap[n - 1]
		char* s = new char[n + 1]; s[n] = '\0'; //字符串所占空间，由上层调用者负责释放
		for (int i = 0; i < n; i++) s[i] = test(i) ? '1' : '0';
		return s; //返回字符串位置
	}

    //若被访问的bitmap[k]已出界，则需扩容
	void expand(int k)
	{ 
		if (k < 8 * N) return; //仍在界内，无需扩容
		int oldN = N; char* oldM = M;
		init(2 * k); //与向量类似，加倍策略
		memcpy_s(M, N, oldM, oldN); delete[] oldM; //原数据转移至新空间
	}

    //逐位打印以检验位图内容，非必需接口
	void print(int n) 
	{
		expand(n);
		for (int i = 0; i < n; i++)
			printf(test(i) ? "1" : "0");
	}

    //判断某个数是否为素数
	static bool isPrime(int n) {  
		if (n <= 3) {
			return n > 1;
		}
		// 不在6的倍数两侧的一定不是质数
		if (n % 6 != 1 && n % 6 != 5) {
			return false;
		}
		int s = (int)sqrt(n);
		for (int i = 5; i <= s; i += 6) {
			if (n % i == 0 || n % (i + 2) == 0) {
				return false;
			}
		}
		return true;
	}
};

（2）std::vector<bool>

但bitset效率极低，做不了bitmap。

而vector<bool>在cpp中不是存储bool的vector，而是被标准库特化为了比特，极大节省了空间且效率极高。

（3）应用场景

• 有500万个数字，数字分布在范围1000w~1500w内，要求排序且复杂度为O(N)，查找数字且复杂度为O(1)

  #include <iostream>
  #include <stdlib.h>
  #include <vector>
  #include <random>
  #include <string>
  
  #define MIN 10000000	//数据下限
  #define MAX 14999999	//数据上限（右闭区间）
  #define COUNT 5000000	//数据个数
  
  int main()
  {
      using namespace std;
      std::random_device rd;  //如果可用的话，从一个随机数发生器上获得一个真正的随机数
      std::mt19937 gen(rd()); //gen是一个使用rd()作种子初始化的标准梅森旋转算法的随机数发生器
      std::uniform_int_distribution<> distrib(MIN, MAX);
  
      vector<bool> bitmap(MAX - MIN + 1, false);	//全部置0
      printf("capacity=%d,size=%d\n", bitmap.capacity(), bitmap.size());
  
      for (int i = 0; i < COUNT; i++)
      {
          int index = distrib(gen) - MIN;	//原始数据要减去MIN映射到0~MAX-MIN的区间上
          bitmap[index] = true;	
      }
  
      while (true)
      {
          cout << "input:" << endl;
          int a;
          cin >> a;
          if (a<MIN || a>MAX)
          {
              cout << to_string(a) << " is not existed..\n";
              continue;
          }
  
          if (bitmap[a - MIN])
              cout << to_string(a)<< "is existed..\n";
          else
              cout << to_string(a)<< "is not existed..\n";
      }
  
      /*int count = 0;
      for(auto item:bitmap)
      { 
          if (++count == 100)
          {
              cout << endl;
              count = 0;
          }
  
          if (item)
              printf("1");
          else
              printf("0");
  
      }
      cout << endl;
      printf("capacity=%d,size=%d\n", bitmap.capacity(), bitmap.size());*/
  
      return 0;
  }
  

  #include <iostream>
  #include <stdlib.h>
  #include <vector>
  #include <random>
  #include <string>
  #include "Bitmap.h"
  
  #define MIN 10000000
  #define MAX 14999999
  #define COUNT 5000000
  
  int main()
  {
      using namespace std;
      std::random_device rd;  //如果可用的话，从一个随机数发生器上获得一个真正的随机数
      std::mt19937 gen(rd()); //gen是一个使用rd()作种子初始化的标准梅森旋转算法的随机数发生器
      std::uniform_int_distribution<> distrib(MIN, MAX);
  
      Bitmap bitmap(COUNT);
  
      for (int i = 0; i < COUNT; i++)
      {
          int index = distrib(gen) - MIN;
          bitmap.set(index);
      }
  
  
      for (int i = 0; i < (MAX - MIN); i++)
      {
          if (bitmap.test(i))
          {
              cout << "min=" << i + MIN << endl;
              break;
          }
      }
  
      for (int i = MAX - MIN - 1; i >= 0; i--)
      {
          if (bitmap.test(i))
          {
              cout << "max=" << i + MIN << endl;
              break;
          }
      }
  
      //bitmap.print(COUNT);
  
      while (true)
      {
          cout << "input:" << endl;
          int a;
          cin >> a;
          if (a<MIN || a>MAX)
          {
              cout << to_string(a) << " is not existed..\n";
              continue;
          }
  
          if (bitmap.test(a-MIN))
              cout << to_string(a)<< "is existed..\n";
          else
              cout << to_string(a)<< "is not existed..\n";
      }
  
      return 0;
  }
  

• 40亿个非负整数中算中位数和找出现两次的数