手写Bitset优化
2024-09-05 05:21:24
一种优化方法，具体例子可以看这里
这里只是存一下手写Bitset的板子
struct Bitset
{
unsigned a[1600];
void reset()
{
memset(a,0,sizeof(a));
}
Bitset()
{
reset();
}
void flip(int x)
{
a[x>>5]^=1<<(x&31);
}
void set(int x)
{
a[x>>5]|=1<<(x&31);
}
void reset(int x)
{
a[x>>5]&=~(1<<(x&31));
}
int test(int x)
{
return (a[x>>5]>>(x&31))&1;
}
Bitset operator ~()const
{
Bitset ret;
for(int i=0;i<1600;i++)ret.a[i]=~a[i];
return ret;
}
Bitset operator &(const Bitset &b)const
{
Bitset ret;
for(int i=0;i<1600;i++)ret.a[i]=a[i]&b.a[i];
return ret;
}
Bitset operator |(const Bitset &b)const
{
Bitset ret;
for(int i=0;i<1600;i++)ret.a[i]=a[i]|b.a[i];
return ret;
}
Bitset operator ^(const Bitset &b)const
{
Bitset ret;
for(int i=0;i<1600;i++)ret.a[i]=a[i]^b.a[i];
return ret;
}
Bitset operator <<(const int t)const
{
Bitset ret;
unsigned last=0;
int high=t>>5,low=t&31;
for(int i=0;i+high<1600;i++)
{
ret.a[i+high]=last|(a[i]<<low);
if(low)last=a[i]>>(32-low);
}
return ret;
}
Bitset operator >>(const int t)const
{
Bitset ret;
unsigned last=0;
int high=t>>5,low=t&31;
for(int i=1600-1;i>=high;i--)
{
ret.a[i-high]=last|(a[i]>>low);
if(low)last=a[i]<<(32-low);
}
return ret;
}
vector<int> ones()const
{
vector<int> ret;
for(int i=0;i<1600;i++)
{
unsigned tmp=a[i];
while(tmp)
{
short t=__builtin_ctz(tmp);
ret.pb((i<<5)|t);
tmp^=1u<<t;
}
}
return ret;
}
}use,trans,cur;
最新文章
- iOS学习笔记——多控制器管理
- 迭代器和for-of循环 顺便带一下Es5中的.map遍历
- HDU 2602 Bone Collector WA谁来帮忙找找错
- BestCoder12 1001.So easy(hdu 5058) 解题报告
- 深度解析国内O2O模式
- vim之pydiction插件
- URL地址下载图片到本地
- robotframework-FQA
- html页面布局 第8节
- 爱加密Android APk 原理解析
- Java设计模式---工厂模式（简单工厂、工厂方法、抽象工厂）
- 清明培训 清北学堂 DAY1
- Python：Day55 ORM多表操作
- orcle查看表空间数据文件使用情况
- Object type TYPE failed to create with error
- Swift - EasingAnimation绘制圆环动画
- BZOJ2878 NOI2012迷失游乐园（树形dp+环套树+概率期望）
- Tomcat *的安装和运行（绿色版和安装版都适用）
- 深度学习方法（九）：自然语言处理中的Attention Model注意力模型
- BZOJ5249：[九省联考2018]IIIDX——题解