这几天遇到了一种特殊的动态规划—-数位DP。做的我头痛欲裂，连忙过来写一篇有关位运算的文章，看看它的神奇之处。

在C++中有”与&、或|、非~、异或^、右移>>、<<左移”这六种运算符。但实际在二进制的算法中远不止这些。

---

1.0 基本运算

1.1 运算前提

使用二进制保存信息，代表这是一个集合，而不是该二进制的真实数字，例如101，在这里代表的是集合{0, 2}，而不是5

1.2 空集、单元集、全集和补集（初始化）

• 空集 ∅ 就是全空，也就是 res = 0;
• 单元集，即单个元素的集合，例如我需要 4 ，也就是 10000，只需要 res = 1 << 4; 即可
• 全集，指的是从 0 到指定数字的所有元素，res = (1 << n) - 1; 可以获取从 0 ~ n – 1 的所有元素
• 补集，把 s 在指定数字内所有欠缺元素指出，res = ((1 << n) - 1) ^ s;

1.3 属于与不属于（检查元素是否在s中）

res = (s >> i) & 1; res为 1 是属于，为 0 便是不属于。

1.4 添加/删除元素

• 添加元素，往 s 中添加元素 i res = s | (1 << i);
• 删除元素，删除 s 中的元素 i（可能不在集合 s 中）res = s &~ (1 << i);
• 删除元素，删除 s 中的元素 i（一定在集合 s 中）res = s ^ (1 << i);

---

2.0 进阶运算

2.1 计算集合大小

即计算 s 中 1 的数量，使用C++内置复杂度为 O( 1 ) 函数。res = __builtin_popcount(s);

2.2 计算二进制长度

res = __lg(s) + 1; 注意lg(0)是非法行为。

2.3 集合最大元素

res = __lg(s);

2.4 lowbit（集合最小元素）

lowbit，顾名思义就是获取最小（最右边的 1 ）的元素，lowbit(s) = s & ~s;

例如 s = 1010，在lowbit运算之后就是 0010，获取了最右边的 1 元素所在的位置

在C++内置函数中，也可以使用 res = __builtin_ctz(s);

2.5 删除lowbit元素

删除最小的元素，其他保持不变。delete(s) = s & (s - 1);

---

3.0 遍历与枚举

3.1 遍历集合

for(int i = 0; i < n; i ++){
    if((s >> i) & 1){
        // 处理 s
    }
}

3.2 枚举全集

for(int s = 0; s < (1 << n); s ++) {
    // 处理 s
}

3.3 枚举非空子集

for(int sub = s; sub; sub = (sub - 1) & s) {
    // 处理 sub
}

3.4 枚举含空子集

int sub = s;
do {
    // 处理 sub
    sub = (sub - 1) & s;
} while (sub != s);

3.5 枚举超集

如果 T 是 S 的子集，那么称 S 是 T 的超集（superset）。

for (int s = t; s < (1 << n); s = (s + 1) | t) {
    // 处理 s
}

---

4.0 总结

首先是资料整理的来源，部分内容来自于网络收集，3.0的内容借鉴了灵茶山艾府的整理。

整理的过程中，我确实理解到了二进制的妙处。接触位运算的感觉其实就是”简单 -> 好难 -> 不想学 -> 有点意思 -> 悟了”的过程。所以如果无法理解大佬解释的话，就先打好基础，了解用途，然后再去慢慢理解就好辣~

有兴趣的话可以观看我的以往文章(还没多少欸）。博客还在持续更新中，敬请期待~