当前位置：首页 > news >正文

位图--Bitset【0基础详细版】

news 2025/6/3 17:02:58

文章目录

概念
bitset
初始化和构造
运算操作
访问
常用方法函数
例题训练
- M - 第九届河北省大学生程序设计竞赛
总结

概念

位图 用一个二进制位（0或1）来标记某个状态或资源是否被占用。
第i个元素为0：第i个元素不存在/未被占用。
第i个元素为1：第i个元素存在/被占用。

bitset

简单来说就是01数组或者说是01字符串，然后赋予了整体的一些位运算操作。
优点：
以位为单位存储，空间复杂度较低。

初始化和构造

一、无参数构造

bit<4>b;//默认构造，所有位初始化为0.
bitset<32>b1;//32是长度，也可以是其他，不够前补0.

二、传入int参数构造

bitset<9>b2(12);//12=000000001100.
//传入一个整数按二进制初始化，不够前补0。

三、传入字符串参数构造

string s1="1001010";
char s2[]="1000111";
bitset<10>b3(s1);//"1001010"="0001001010"
bitset<10>b4(s2);//"1000111"="0001000111"
//传入字符串初始化时，填充位数不足的部分为0。

代码展示

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{string s1="111001";bitset<4>b;//0000bitset<8>b1(9);//00001001bitset<10>b2(s1);//0000111001cout<<b<<'\n'<<b1<<'\n'<<b2<<'\n';return 0;}

结果展示
在这里插入图片描述

运算操作

bitset类似数组和字符串，在bitset容器中，不仅基本的赋值运算符（=）和一些关系运算符（==、!=）被重载，还对一些复合赋值运算符（&=、|=、^=、<<=、>>=）和单目运算符（~）进行了重载，当然肯定也是支持位运算的。这使得我们可以直接使用这些运算符来对bitset对象（即位图）进行各种操作，如位的赋值、比较、逻辑运算、位移以及取反等。
例如，以下代码主要展示了如何使用位运算符：

#include<bits/stdc++.h>
using namespace std;
int main()
{bitset<8>b1("10101100");bitset<8>b2("11100100");bitset<8>b3;b3=b1&b2;cout<<"b1&b2= "<<b3<<endl;b3=b1|b2;cout<<"b1|b2= "<<b3<<endl;b3=b1^b2;cout<<"b1^b2= "<<b3<<endl;b3=~b1;cout<<" ~ b1= "<<b3<<endl;b3=b1<<2;cout<<"b1<<2= "<<b3<<endl;b3=b2>>2;cout<<"b2>>2= "<<b3<<endl;return 0;}

在这里插入图片描述

访问

bitset容器还重载了**[ ]运算符**，允许我们直接通过索引来访问或修改bitset中指定位置的位。

#include<bits/stdc++.h>
using namespace std;
int main()
{bitset<8>b("10101100");for(int i=0;i<8;i++)cout<<b[i];cout<<endl; b[2]=0,b[3]=1;cout<<"b[2]:"<<b[2]<<endl;cout<<"b[3]:"<<b[3]<<endl;return 0;}

在这里插入图片描述

常用方法函数

成员函数	功能
`set`	设置指定位或所有位为1（即设置为“已设置”状态）
`reset`	清空指定位或所有位，将其设为0（即设置为“未设置”状态）
`flip`	反转指定位或所有位的状态。如果位是0，则变为1；如果位是1，则变为0
`test`	获取指定位的状态。如果位是1，则返回`true`；如果位是0，则返回`false`
`count`	获取被设置为1的位的个数（即“已设置”的位数数量）
`size`	获取位置可以容纳的位的总数。这通常指的是位置数组的最大小（以位为单位）
`any`	如果有任何一个位被设置为1（即至少有一个位是“已设置”状态），则返回`true`；否则返回`false`
`none`	如果没有位被设置为1（即所有位都是“未设置”状态），则返回`true`；否则返回`false`
`all`	如果所有位都被设置为1（即所有位都是“已设置”状态），则返回`true`；否则返回`false`

例题训练

M - 第九届河北省大学生程序设计竞赛

在这里插入图片描述

这道题就巧妙的运用了bitset，非常方便
代码比较详细：

#include<bits/stdc++.h>
#define int long long
using namespace std;
#define endl '\n'
const int N=1005;
int ra,rb,rc,pa,pb,pc,n,m;
string s[N];
void solve()
{cin>>n>>m;for(int i=1;i<=m;i++)cin>>s[i];cin>>ra>>rb>>rc;cin>>pa>>pb>>pc;for(int i=1;i<=(1<<n)-1;i++)//(1<<n)即2的n次方{//在二进制中，2^n的二进制表示的刚好时n+1位数//因为在二进制中2^n次方是1后面跟n个0，所以当2^n用二进制表示时，其位数为n+1bitset<20>bt(i);//将i转化为二进制if(bt.count()>=10&&bt.count()<=13)//题中给了n是10~13道题目，所以可以适当剪枝，减少时间复杂度{vector<int>a;a.push_back(1e18);//维护下标，为了使下标从1开始for(int j=1;j<=m;j++){bitset<20>c(s[j]);//初始化c为01串s[j]c&=bt;//进行且操作，找出两个二进制数中的共同的1的个数a.push_back(c.count());//c.count()表示c中1的个数 } sort(a.begin(),a.end(),greater<int>());//从大到小排序 if(a[ra]==pa&&a[rb]==pb&&a[rc]==pc)// 如果满足题目要求，即当前位次的过题数符合题意{cout<<bt.count()<<endl;//输出一样的个数 for(int j=n-1;j>=0;j--){if(bt[j])//如果为1，输出题目下标 cout<<n-j<<" "; } return ;} } } cout<<-1<<endl;return ;
}
signed main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);solve();return 0;}