对于位运算最好的方式,就是把int看作32位的数组,除此stl也提供了bitset,
NOTE: 注意逻辑非/按位反>移位>单逻辑>双逻辑
位运算基础
int x;
// 查询:
x >> i & 1; // 获取第i位的值
// 或者
x & 1 << i;
// 更新:
x |= 1 << i; // 在第i位上加上1(置1)
x &= ~(1 << i) // 在第i位减去1(置0)
x ^= 1 << i // flip(置反)
// 遍历:
for (int i = 0; i < 32; i++) int t = x >> i & 1;
// lowbit
x & -x
// lowbit遍历
for (;x;x-=lowbit(x)) int t = lowbit(x)
// bitset定义
bitset<M> s;
// bitset 查询
s[i];
s.any(); // 还存在1
s.none(); // 全为0
// bitset 更新
s[i] = 0;
s[i] = 1;
s[i].flip();
// 位操作
s1 & s2
s1 | s2
s1 ^ s2
位运算与图论:
对于无向图,用0,1存两个方向
// s和s^1分别代表成对的两条边
void add(int a, int b, int v) {
e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx++;
}
// 这样通过s^1就可以获得反方向边
位运算与堆式存储
s^t^1 // 是否为兄弟节点
s^1 // 获取兄弟节点
s << 1 // 左儿子
s << 1 | 1 右儿子
s >> 1 // 父亲
强