更多精彩内容,请关注微信公众号:后端技术小屋

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?

推荐阅读

更多精彩内容,请扫码关注微信公众号:后端技术小屋。如果觉得文章对你有帮助的话,请多多分享、转发、在看。
二维码