0001 struct Bitmap { //位图Bitmap类
0002    unsigned char* M;  Rank N, size; //数组M共有8*N个bit，其中size位为1，其余为0
0003    void init(Rank n) { M = new uint8_t[N = (n+7)/8];  memset(M, 0, N); } //初始化
0004    Bitmap(Rank n = 64) { init(max(64U, n));  size = 0; } //构造
0005    ~Bitmap() { delete[] M; } //析构
0006    void reset() { memset(M, 0, N);  size = 0; } //O(n)，待改进
0007    bool  test(Rank k) {    expand(k);  return  M[k>>3]  &  (0x80 >> (k & 0x07)); }
0008    void   set(Rank k) { if (test(k)) return;  M[k>>3] |=  (0x80 >> (k & 0x07));  size++; }
0009    void clear(Rank k) { if (!test(k)) return;  M[k>>3] &= ~(0x80 >> (k & 0x07));  size--; }
0010    void expand(Rank k) { //若被访问的[k]已出界，则需扩容
0011       if (k < 8*N) return; //仍在界内，无需扩容
0012       Rank oldN = N;  unsigned char* oldM = M;  init(2*k); //容量加倍
0013       memcpy_s(M, N, oldM, oldN);  delete[] oldM; //搬迁原数据、释放原空间
0014    } //expand
0015 }; //Bitmap