手写 bitset

首先确定 bitset 的大小，假如是 \(n\)。令 len = n>>6。

开 ull bs[(MAXN>>6)+5]。

访问某一位

假设访问第 \(x\) 位。写作 bs[x>>6]>>(x&63)&1。

修改某一位

假设要将第 \(x\) 位异或 \(1\)。写作 bs[x>>6]^=1ull<<(x&63)。

两个 bitset 之间的操作

另有一个 bitset 叫 sb，以或为例，写作 for(int k=0;k<=m;k++) bs[k]|=sb[k]。

遍历 bitset 里所有的 1

从高位到低位：

for(int k=len;~k;k--){ull msk=bs[k];while(msk){int u=(k<<6)+__lg(msk);// 第u位 ...msk^=1ull<<__lg(msk); }
}

从低位到高位：

for(int k=0;k<=len;k++){ull msk=bs[k];while(msk){int u=(k<<6)+__builtin_ctzll(msk);// 第u位 ...msk&=msk-1; }
}