bitset用法

Accoty_AM · 2023-09-11 15:37:24 · 个人记录

//bitset 用法
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define per(i, a, b) for(int i = a; i >= b; --i)
//以下函数时间复杂度皆为O(1)
//__builtin_popcount(unsigned int x) x 二进制中 1 的个数()
//__builtin_popcountll(unsigned int x) x 二进制中 1 的个数() long long 版本
//__builtin_parity(x) x 二进制中 1 的个数的奇偶性
//__builtin_parityll(x) x 二进制中 1 的个数的奇偶性 long long 版本
//__builtin_ctz(x) x 二进制 末尾的 0 的个数
//__builtin_clz(x) x 二进制 开头的 0 的个数
//(int)log2(x) = 31 - __builtin_clz(x)

const int N = 1000;
//bool a[N]; a[i] 占用一个 byte，bitset 则占用一个 bit
bitset<N> x;

//x.any() x 里是否存在一个 1 O(n / w)
//x.none() = !x.any() O(n / w)
//x.count() 统计里面有几个 1 O(n / w)

//x.set(a) 把 a 这一位变成 1
//x.set() 把所有位变成 1
//x.reset(a) 把 a 这一位变成 0
//x.reset() 全变成 0
//x.flip(a) 反转第 a 位
//x.flip(a) a 全取反 = ~a

//_Find_first, _Find_next 找到第一个等于 1 的位置，找到下一个等于 1 的位置
//for(int i = B._Find_first(); i != B.size(); i = B._Find_next(i)) 遍历所有 1 O(n / w + 1的个数)

//(unsigned long long *)&a; 转换成 unsigned long long 数组去用
//x.to_string() 高位在前，低位在后

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    return 0;
}