- 1 相关头文件
- 2 bitset
- 2.1 数据结构
- 2.2 重要接口
1 相关头文件
bitset
2 bitset
bitset中STL中用于表示位图的容器，它支持读写特定bit、从整数或字符串生成bitset对象。bitset大小通过模板参数指定，一旦编译器确定便无法变更，这一点与vector<bool>有差异。
2.1 数据结构
bitset是_Base_bitset的派生类。_Base_bitset中包含一个长度_Nw，类型unsigned long的数组，其中_Nw通过模板参数指定。在64位系统中，unsigned long长度为8 Byte。
注意，这里_Nb不一定是8 * sizeof(unsigned)的整数倍，所以需要宏__BITSET_WORDS对其进行向上取整操作。
template<size_t _Nb> class bitset : private _Base_bitset<__BITSET_WORDS(_Nb)> { private: typedef _Base_bitset<__BITSET_WORDS(_Nb)> _Base; typedef unsigned long _WordT; ... } template<size_t _Nw> struct _Base_bitset { typedef unsigned long _WordT; _WordT _M_w[_Nw]; // 0 is the least significant word. ... }
2.2 重要接口
- 从整数构造bitset
首先对数组清零，然后将__val值赋给数组的首个元素。最后使用_M_do_sanitize判断_Nb是不是sizeof(unsigned long)的整数倍，否则将right padding bits全部置为1。
bitset(unsigned long __val) : _Base_bitset<__BITSET_WORDS(_Nb)>(__val) { _M_do_sanitize(); } _Base_bitset(unsigned long __val) { _M_do_reset(); _M_w[0] = __val; } void _M_do_sanitize() { _Sanitize<_Nb%__BITS_PER_WORD>::_M_do_sanitize(this->_M_hiword()); } template <size_t _Extrabits> struct _Sanitize { static void _M_do_sanitize(unsigned long& __val) { __val &= ~((~static_cast<unsigned long>(0)) << _Extrabits); } }; __STL_TEMPLATE_NULL struct _Sanitize<0> { static void _M_do_sanitize(unsigned long) {} };
- 从字符串构造bitset
由字符'0', '1'组成的字符串构造bitset。注意: 字符串从左到右，对应的bit在bitset中从右到左。因为字符串中, 左边为高位，bitset中右边为高位。
explicit bitset(const basic_string<char>& __s, size_t __pos = 0, size_t __n = basic_string<char>::npos) : _Base() { if (__pos > __s.size()) __STL_THROW(out_of_range("bitset")); _M_copy_from_string(__s, __pos, __n); }
- to_ulong: 将bitset转化为ulong类型
- to_string: 将bitset转化为'0' '1'组成的字符串
- <<=: 逻辑左移，移出部分补零。注意：在实现上，数组
_M_w中低位对应bitset中低位，因此，对bitset的左移操作其实就是对数组的右移操作，右移同理。如果移动位数是8 * sizeof(unsigned long)的整数倍，则直接移动数组中元素即可。
const size_t __sub_offset = __BITS_PER_WORD - __offset; for (size_t __n = _Nw - 1; __n > __wshift; --__n) _M_w[__n] = (_M_w[__n - __wshift] << __offset) | (_M_w[__n - __wshift - 1] >> __sub_offset); _M_w[__wshift] = _M_w[0] << __offset; }
- >>=: 逻辑右移
const size_t __sub_offset = __BITS_PER_WORD - __offset; for (size_t __n = 0; __n < __limit; ++__n) _M_w[__n] = (_M_w[__n + __wshift] >> __offset) | (_M_w[__n + __wshift + 1] << __sub_offset); _M_w[__limit] = _M_w[_Nw-1] >> __offset;
- |=: 按位或
- &=: 按位与
- ^+: 按位异或
- set: 置位
- reset: 清零
- flip: 翻转
- ~: 全部翻转
- count: count为了快速计算bitset中1的个数，使用了查找表的技巧。查找表中key为byte值，value为该byte值中1的个数。count方法遍历数组中每个字节，通过查找表计算每个字节中1的个数，并累加之。
- size: 返回bitset大小
- test: 判断bitset中某位是否为1
- any: 判断bitset中是否有至少一个1
- none: 同any相反
- all: 判断bitset中是否全为1
留下问题给读者思考：为何bitset中的数组类型是unsigned long而非unsigned char?
