在蒟蒻Cydiater日常水题的过程中，忽然遇到了一道题。中间有一个过程是要求在很快的时间内求出$1500$大小的两个01串的与之后存在多少个1。

最坏的，扫一遍，整体复杂度$O(N)$,好像没有什么可以优化的空间了QAQ。我开始考虑用位运算的与操作优化，因为其有$1500$个元素，所以可以考虑把这个东西拆成$\frac{N}{32}$个01串。

但是这之后好像就又存在一个问题。如何快速的统计一个二进制的01串里有多少个1？如果不要求$O(1)$,可以不停的统计lowbit,那么这个复杂度就和有多少个答案有关，这样的话最坏复杂度仍然是$O(N)$.

然后就去百度各种翻，看到了一个关于bitset的名词。然后xjb搞了搞后觉得很神奇，就先记下来。

BITSET

bitset是STL里的一种容器，也就是一个优化过的bool数组。里面存的就是一大串的01。

之所以说它优化过，是因为他不仅可以像int和long long一样进行与，或，异或操作。时间复杂度也大差不差。而且自带的一些函数也很方便使用，其中就包括了快速的统计出来一个bitset里有多少个1。

bitset的具体操作有很多，我列举几个比较常用的。

具体的定义如下：

#include <bitset>using namespace std;#define LENGTH 32#define bs bitset<LENGTH>bs S;

这里面的LENGTH就是要定义的长度，也就是里面具体有几个01元素。

因为他重载了[],所有可以像访问数组一样访问任意位。

复制一段别人的代码：

#include <iostream>  #include <bitset>  using namespace std;    int main(){      //bitset 使用整数初始化bitset      bitset<3> bs(7);      //输出bs各个位的值      cout<<"bs[0] is "<<bs[0]<<endl;      cout<<"bs[1] is "<<bs[1]<<endl;      cout<<"bs[2] is "<<bs[2]<<endl;      //下面的语句会抛出outofindexexception      //cout<<"bs[3] is "<<bs[3]<<endl;        //使用字符串初始化bitset      //注意：使用string初始化时从右向左处理，如下初始化的各个位的值将是110，而非011      string strVal("011");      bitset<3> bs1(strVal);      //输出各位        cout<<"bs1[0] is "<<bs1[0]<<endl;      cout<<"bs1[1] is "<<bs1[1]<<endl;      cout<<"bs1[2] is "<<bs1[2]<<endl;      //cout输出时也是从右边向左边输出      cout<<bs1<<endl;        //bitset的方法      //any()方法如果有一位为1，则返回1      cout<<"bs1.any() = "<<bs1.any()<<endl;        //none()方法，如果有一个为1none则返回0，如果全为0则返回1      bitset<3> bsNone;      cout<<"bsNone.none() = " <<bsNone.none()<<endl;        //count()返回几个位为1      cout<<"bs1.count() = "<<bs1.count()<<endl;        //size()返回位数      cout<<"bs1.size() = "<<bs1.size()<<endl;        //test()返回某一位是否为1      //flip()诸位取反      bitset<3> bsFlip = bs1.flip();      cout<<"bsFlip = "<<bsFlip<<endl;        //to_ulong      unsigned long val = bs1.to_ulong();      cout<<val;  }  

位运算的另一种姿势