首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >bitset用法小结

bitset用法小结

作者头像
attack
发布2018-04-13 16:08:25
1.3K0
发布2018-04-13 16:08:25
举报

bitset

bitset大概就是类似于bool数组一样的东西

但是它的每个位置只占1bit(特别特别小)

bitset的原理大概是将很多数压成一个,从而节省空间和时间(暴力出奇迹)

一般来说bitset会让你的算法复杂度 /32(具体是什么要看计算机)

定义与初始化

使用bitset类型需#include<bitset>

bitset类型在定义时就需要指定所占的空间,例如

bitset<233>bit;

bitset类型可以用string和整数初始化(整数转化成对应的二进制)

#include<iostream>
#include<bitset>
#include<cstring>
using namespace std;
int main()
{
    bitset<23>bit (string("11101001"));
    cout<<bit<<endl;
    bit=233;
    cout<<bit<<endl;
    return 0;
}

输出结果

00000000000000011101001
00000000000000011101001

基本运算

bitset支持所有位运算

bitset<23>bita(string("11101001"));
bitset<23>bitb(string("11101000"));
cout<<(bita^bitb)<<endl;
//输出00000000000000000000001 
bitset<23>bita(string("11101001"));
bitset<23>bitb(string("11101000"));
cout<<(bita|bitb)<<endl;
//输出00000000000000011101001
bitset<23>bita(string("11101001"));
bitset<23>bitb(string("11101000"));
cout<<(bita&bitb)<<endl;
//输出00000000000000011101000
bitset<23>bit(string("11101001"));
cout<<(bit<<5)<<endl;
//输出00000000001110100100000
bitset<23>bit(string("11101001"));
cout<<(bit>>5)<<endl;
//输出00000000000000000000111

常用函数

对于一个叫做bit的bitset:
bit.size()       返回大小(位数)
bit.count()     返回1的个数
bit.any()       返回是否有1
bit.none()      返回是否没有1
bit.set()       全都变成1
bit.set(p)      将第p + 1位变成1(bitset是从第0位开始的!) 
bit.set(p, x)   将第p + 1位变成x
bit.reset()     全都变成0
bit.reset(p)    将第p + 1位变成0
bit.flip()      全都取反
bit.flip(p)     将第p + 1位取反
bit.to_ulong()  返回它转换为unsigned long的结果,如果超出范围则报错
bit.to_ullong() 返回它转换为unsigned long long的结果,如果超出范围则报错
bit.to_string() 返回它转换为string的结果

题目

这玩意儿其实挺实用的,

一般用来优化奇偶性有关的问题,或者判断联通性之类的,(或许还可以在搜索的时候优化一下访问标记?)

BZOJ3687

BZOJ4484

快省选了,可以自己还是什么都不会,估计这两天学新算法也没啥意义了,就整理整理语法吧QWQ..

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018-04-02 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • bitset
    • 定义与初始化
      • 基本运算
        • 常用函数
        • 题目
        领券
        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档