bitset 学习笔记 （不定时更新）

· · 个人记录

首先声明一下，文章内容纯属个人理解，可能理解有误或者术语不当，请下方评论指正

//P1441

看到这道题的题解时我直接惊了

不得不说，bitset 真是个好东西，直接把搜索变成模拟，

先来看看代码吧：

int main(void)
{
    cin >> n >> m;
    for(int i=0;i<n;i++)    cin >> a[i];
    for(int i=1;i<=(1<<n)-1;i++)
        if(__builtin_popcount(i) == n-m)
        {
            bitset <100>b;
            b[0] = 1;
            for(int j=0;j<n;j++)
                if(i & (1<<j))
                    b |= b<<a[j];
            ans = max(ans,(int)b.count());
        }
    cout << ans-1;
    return 0;
}

利用 b 来存可以称量出的重量，变成二进制位运算出答案。

既然这么好用，那我们就来好好学学。

首先，bitset 被包含于 < bitset > 头文件中。

然后，就是 bitset 的定义与使用：

bitset <100>b;

//bitset 的使用类似于数组
b[1] = 1;

//也可以进行位运算
cout << (b&1);

那么，让我们来扒一下源文件里有些什么，

好，这次并没有像学 map 时那么难受，找到了一些有用的东西：

1.定义：

The %bitset class represents a @e fixed-size sequence of bits.

bitset 类代表一个固定大小的比特序列。（ @e 不清楚是什么，就不乱讲了）

2.输出：

源文件内有这么一段代码：

#include <bitset>
#include <iostream>
#include <sstream>
using namespace std;
int main()
{
    long          a = 'a';
    bitset<10>  b(a);

    cout << "b('a') is " << b << endl;

    ostringstream s;
    s << b;
    string  str = s.str();
    cout << "index 3 in the string is " << str[3] << " but\n"
         << "index 3 in the bitset is " <<   b[3] << endl;
}

可以看出，直接输出 b 和按下表输出的顺序是反着的

（ ostringstream 就看成是输出好了）

接下来，是一些 bitset 中的操作：

bitset <8>b("10011011");

    cout << b.count() << endl;　　//5　　（count函数用来求bitset中1的位数，foo中共有５个１
    cout << b.size() << endl;　　 //8　　（size函数用来求bitset的大小，一共有８位

    cout << b.test(0) << endl;　　//true　　（test函数用来查下标处的元素是０还是１，并返回false或true，此处foo[0]为１，返回true
    cout << b.test(2) << endl;　　//false　　（同理，foo[2]为０，返回false

    cout << b.any() << endl;　　  //true　　（any函数检查bitset中是否有１
    cout << b.none() << endl;　　 //false　　（none函数检查bitset中是否没有１
    cout << b.all() << endl;　　  //false　　（all函数检查bitset中是全部为１

2018.9.19 15:16