1. bitset类
1.1 私有成员
位图实际上就是一个指定比特位个数的连续内存空间，所以可以用STL内置的容器vector管理，除此之外，理论上任何类型都可以作为元素的类型，只不过为了容易理解，它的每个元素的类型被设定为char。
template<size_t N> // N个比特位 class bitset { private: vector<char> _bits; // 以char为单位管理 };
1. bitset接口
1.1 构造函数
构造一个有N位的位图，并将所有位初始化为0。
由于申请空间时的最小单位是char（1字节），也就是8个比特位。那么对于N个比特位，需要申请N/8+1个char型空间，因为N可能不是8的整数倍。
申请N=20个比特位，需要20/8+1=3个char。
bitset() { _bits.resize(N / 8 + 1, 0); }
1.2 set
要把某个比特位变成1，首先要知道这个比特位在哪个位置。
- 首先计算这个比特位在整个位图中的第x个char；
- 然后计算比特位在这个char的第y个位置；
- 最后将1左移y位和第x个char或运算。
void set(size_t pos) { assert(pos < N); size_t x = pos / 8; // 在x个char size_t y = pos % 8; // 在这个char的第y个比特位 _bits[x] |= (1 << y); // 将这个比特位设为1 }
1.3 reset
要把某个比特位清空，即恢复到0状态，首先要找到它的位置，和set的操作是一样的，只有最后一步不同：
- 首先计算这个比特位在整个位图中的第x个char；
- 然后计算比特位在这个char的第y个位置；
- 最后将1左移y位后，整体取反，再和第x个char与运算。
注意：
使用~对左移后的1按位取反，而不是逻辑取反!。
void reset(size_t pos) { assert(pos < N); size_t x = pos / 8; // 在x个char size_t y = pos % 8; // 在这个char的第y个比特位 _bits[x] &= (~(1 << y)); // 将这个比特位设为0 }
1.4 flip
要把某个比特位取反，首先要找到它的位置：
- 首先计算这个比特位在整个位图中的第x个char；
- 然后计算比特位在这个char的第y个位置；
- 最后将1左移y位后，再和第x个char异或运算。
void flip(size_t pos) { assert(pos < N); size_t x = pos / 8; // 在x个char size_t y = pos % 8; // 在这个char的第y个比特位 _bits[x] ^= (1 << y); // 将这个比特位取反 }
1.5 test
同样地：
- 首先计算这个比特位在整个位图中的第x个char；
- 然后计算比特位在这个char的第y个位置；
- 获取某个位的状态：
- true：已被设置；
- false：未被设置。
void test(size_t pos) { assert(pos < N); size_t x = pos / 8; // 在x个char size_t y = pos % 8; // 在这个char的第y个比特位 if (_bits[x] & (1 << y)) // 该位已被设置 return true; else return false; }
1.6 size、count
- size：获取位图中可以容纳的位的个数。
直接返回模板参数N。
size_t size() { return N; }
- count：获取位图中被设置的位的个数。
要知道位图中被设置为1的位的个数，就是遍历整个位图，统计1的个数。
- 将当前数x与x-1与运算得到新的数x；
- x是否为0：
- 为0：结束；
- 不为0：重复操作。
原因是每进行一次操作1，都会将数x最右端的1消去。那么在x不为0之前，进行了几次消1操作就是位图中1个个数。
size_t count() { size_t count = 0; for (auto e : _bits) { char num = e; while (num) { num &= num - 1; count++; } } return count; }
1.7 any、none、all
- any：判断位图中是否有任何位被设置。
只需要遍历位图中所有的比特位，一旦有1则返回true，否则返回0。但也可以不用这么干，因为一个char里只要有一个不为0，整个char就是其他字符。ASCII=0对应的字符时'\0'，但是它一般用在字符串处理中，个人认为在这里还是将0强转为char比较合适。
bool any() { for (auto e : _bits) { if (e != (char)0) return true; } return false; }
- none：判断位图中是否全部位都没有被设置。
直接复用any的代码，它们是互斥的。
bool none() { return !any(); }
- 判断位图中是否全部位都被设置。
判断全部位置都被设置为1，分为两步：
- 判断所有完整的char中8个比特位是否都为1；
- 判断剩下（可能）不完整的char的所有比特位是否都为1。
同样地，第一步中可以判断这个char是否等于比特位全为1对应的字符，也就是(char)127，遍历剩下的比特位是否为1即可。
bool all() { size_t size = _bits.size(); for (size_t i = 0; i < size - 1; i++) // 前size-1个完整的char { if (_bits[i] != (char)127) return false; } for (size_t i = 0; i < N % 8; i++) // 最后一个char的剩下位 { if ((_bits[size - 1] & (1 << i)) == (char)0) return false; } return true; }
1.8 打印函数
这不是bitset内置的成员函数，因为STL中重载了流输入>>和流输出<<运算符，可以直接打印bitset中的内容，而模拟实现并未重载它们，所以用打印函数输出容器内容。
思路和上一个很类似，也是分批打印：
void Print() { string ret = ""; size_t size = _bits.size(); for (size_t i = 0; i < size - 1; i++) { for (size_t j = 0; j < 8; j++) { if (_bits[i] & (1 << j)) ret += "1"; else ret += "0"; } } for (size_t j = 0; j < N % 8; j++) { if (_bits[size - 1] & (1 << j)) ret += "1"; else ret += "0"; } cout << ret << endl; }
2. bitset测试
void bitset_test1() { xy::bitset<30> bs1; bs1.set(8); bs1.set(9); bs1.set(7); bs1.set(27); bs1.set(20); bs1.Print(); cout << bs1.count() << endl; bs1.reset(8); bs1.reset(9); bs1.reset(20); bs1.Print(); cout << bs1.count() << endl; cout << bs1.any() << endl; bs1.reset(7); bs1.reset(27); bs1.Print(); cout << bs1.none() << endl; }
输出：
000000011100000000001000000100 5 000000010000000000000000000100 2 1 000000000000000000000000000000 1
