Bitmap

Bitmap是一种很省内存的数据结构，其每一个比特位都代表一个数字是否存在。

以下是主要的成员函数

void set(int k);//将整数k加入当前序列
void clear(int k);//将整数k从当前序列清除
bool test(int k);//判断整数k是否属于当前集合

以下是一种可行的实现方式

class 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(){ 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 expand(int k){
        if(k<8*N)  return;
        int oldN = N; char *oldM = M;
        init(2 * k);
        memcpy(M,oldM,oldN);
        delete[] oldM;
    }
};

M是存储数据的集合，之所以采用char,也是从节省内存的角度考虑，因为char型仅仅占据一个字节。N为数组大小，不过容量要比N要大，为Nsizeof(char)8.通过移位操作k>>3可确定对应比特位所属字节所对应的秩，以00000100为例，其移位后变为00000000，其实可以从另一角度理解，k>>3相当于k/8，自然0<=k<=7的都在k[0]中。k & 0x07有上面易知，其代表0x07的二进制表示是00000111，k假设是00001000,即k=8,发现结果是00000000，k=9时，结果是00000001，可以知道k&0x07代表k对应比特位在该字节的位置，之后的0x80 >> (k & 0x07)就显得理所当然，是每个数字代表的掩码mask,若位于第一位其掩码位100000000，k|=mask,将掩码对应的位置置一,k&=~mask，将掩码对应的比特位置零。k&mask，求那个比特位是否为一。位运算是一种很灵活也很快的方法。是时候认真总结下位运算用法。另外因为这种寻秩访问的方式，令Bitmap类的三个操作都是$O(1)$的时间复杂度，所以不论是查找还是加入元素都很快。
以上这种虽然插入和删除很快，但是还有个地方很慢，就是对M的初始化，要对每个位置都置零，我们可以换种实现方法，以空间换时间，毕竟时间复杂度才是第一要素。以下先写出set和test的实现。

class Bitmap{
private:
  int *F; int N;
  int *T；int top;
  inline bool valid(int r){return (0<=r)&&(r<top);}
  Bitmap(int n){
    F = new int[N = n];
    T = new int[N];
    top = 0;
  }
  ~Bitmap(){
    delete[] F, delete[] T;
  }
  inline void set(int k){
    if(test(k))
      return;
    F[k] = top++;
    T[F[k]] = k;
  }
  inline bool test(int k){
    return vaild(F[k]) && T[F[k]] == k;
  }
};

F[]是用来存储每个数字对应栈的顺序，T[]中存储数位同时也是F[]中的秩，
此时F[]和T[]组成校验环，即T[F[k]]==k.我们还没实现clear，是否可以简单的调用set接口，将校验环置为-1，答案是不行，因为每次添加set,都会造成栈增加一，长此以来势必会造成栈溢出。
我们应该对曾经入栈的，又被删除的元素添加一标记，每次只对未入栈的元素进行栈加一。

class Bitmap{
private:
  int *F; int N;
  int *T；int top;
  inline bool valid(int r){return (0<=r)&&(r<top);}
  inline bool erased(int r){ return vaild(F[k]) && !(T[F[k]] + 1 + k); }
  Bitmap(int n){
    F = new int[N = n]; T = new int[N];
    top = 0;
  }
  ~Bitmap(){
    delete[] F, delete[] T;
  }
  inline void set(int k){
    if(test(k))  return;
    if(!erased(k))
    F[k] = top++;  T[F[k]] = k;
  }
  inline bool test(int k){
    return vaild(F[k]) && T[F[k]] == k;
  }
  inline void valid(int k){
    if(test(k)) T[F[k]] = -1 - k;
  }
};