即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

C++bitset原理和用法解析

编程语言 stay_the_course 14℃ 0评论

位图(bitset)的原理就是利用每个比特位的0/1这两种状态来表示存在或者不存在这两种状态,比如:有在0~100之间的不重复整数80个,如何判断哪些数在,通常用一个array[100],用这80个数来做array的下标,将存在的下标置为1,遍历数组就能知道知道哪些数据在,但是当数据量比较大的时候,这种方法就显得比较浪费,甚至不可行,比如有40亿个不重复的整数,此时前面的方法明显不可行,因为这些数放进内存就要占约15G的内存,所以我们对每一个比特位进行编址(如下图),用它们的0表示不存在,用1表示存在,如此一来就缩小到约500M的内存就可以解决这个问题:


这里写图片描述

下面看模拟实现:

class BitSet
{

public:
    BitSet(size_t n)
    {
        _table.resize((n>>5)+1, 0);
    }

    void Set(const int& num)
    {
        size_t index = num >> 5;
        size_t pos = num % 32;

        _table[index] |= (1 << pos);
    }

    void Reset(const int& num)
    {
        size_t index = num >> 5;
        size_t pos = num % 32;
        _table[index] &= ~(1 << pos);
    }


protected:
    vector<int> _table;     
//  这里以int为例便于模拟实现(一个int,4个字节,可以表示32个数),
//  实际则可以控制输入所需的位数(详见后续)

};

下面看标准库中的用法解析:

void STL_bitset()
{

    // bitset b;b有n位,每位都为0.参数n可以为一个表达式.

    bitset<5> b0;
        cout <<"b0: "<< b0 << endl;     //则"b0"为"00000";

    // bitset b(unsigned long u);b有n位, 并用u赋值;如果u超过n位, 则顶端被截除

        bitset<5> b1(5);
        cout << "b1: " << b1 << endl;;  //则"b1"为"00101";

    // bitset b(string s);b是string对象s中含有的位串的副本
        string bitval("10011");
    bitset<5> b2(bitval,4);
    cout << "b2: " << b2 << endl;           //则"b2"为"10011";


    //  bitset b(s, pos);b是s中从位置pos开始位的副本, 前面的多余位自动填充0;
    string bitval3("01011010");
    bitset<10> b3(bitval3, 3);
    cout << "b3: " << b3 <//则"b3" 为 "0000011010";

    //  bitset b(s, pos, num);b是s中从位置pos开始的num个位的副本, 如果num
    string bitval4("11110011011");
    bitset<6> b4(bitval4, 3, 6);
    cout << "b4: " << b4 << endl;           //则"b0" 为 "100110";

    // 流
    // os << b
    //  把b中的位集输出到os流
    //  os >> b
    //  输入到b中, 如"cin>>b", 如果输入的不是0或1的字符, 只取该字符前面的二进制位.





    //   属性方法比较简单,基本可以见名知意,不验证
    //  bool any()
    //  是否存在置为1的二进制位 ? 和none()相反

    //  bool none()
    //  是否不存在置为1的二进制位, 即全部为0 ? 和any()相反.

    //  size_t count()
    //  二进制位为1的个数.

    //  size_t size()
    //  二进制位的个数

    //  flip()
    //  把所有二进制位逐位取反

    //  flip(size_t pos)
    //  把在pos处的二进制位取反

    //  bool operator[](size_type _Pos)
    //  获取在pos处的二进制位

    //  set()
    //  把所有二进制位都置为1

    //  set(pos)
    //  把在pos处的二进制位置为1

    //  reset()
    //  把所有二进制位都置为0

    //  reset(pos)
    //  把在pos处的二进制位置为0

    //  test(size_t pos)
    //  在pos处的二进制位是否为1 ?

    //  unsigned long to_ulong()
    //  用同样的二进制位返回一个unsigned long值

    //  string to_string()
    //  返回对应的字符串.

    //

}

运行结果:


这里写图片描述

转载请注明:CodingBlog » C++bitset原理和用法解析

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情