本文主要是介绍集合论与位运算之间的转换，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
集合可以用二进制表示，二进制从低到高第 i 位为 1 表示 i 在集合中，为 0 表示 i 不在集合中。例如集合 {0,2,3} 可以用二进制数 1101(2) 表示；反过来，二进制数 1101(2) 就对应着集合 {0,2,3}。
例如集合 {0,2,3} 可以压缩成 20+22+23=13，也就是二进制数 1101(2)。
一、集合与集合
其中 & 表示按位与，| 表示按位或，⊕ 表示按位异或，~ 表示按位取反。
两个集合的「对称差」是只属于其中一个集合，而不属于另一个集合的元素组成的集合，也就是不在交集中的元素组成的集合。
注 1：按位取反的例子中，仅列出最低 4个比特位取反后的结果，即 0110 取反后是 1001。
注 2：包含于的两种位运算写法是等价的，在编程时只需判断其中任意一种。
注 3：编程时，请注意运算符的优先级。例如 == 在某些语言中优先级比位运算更高。
二、集合与元素
在处理集合与元素的关系时，通常会用到移位运算。
其中 << 表示左移，>> 表示右移。
注：左移 i 位相当于乘以 2i，右移 i 位相当于除以 2i（注意，这里的除法指的是整数除法，即结果向下取整）。
s = 101100s-1 = 101011 // 最低位的 1 变成 0，同时 1 右边的 0 都取反，变成 1
s&(s-1) = 101000
特别地，如果 s 是 2 的幂，那么 s&(s−1)=0。
此外，编程语言提供了一些和二进制有关的库函数，例如：
- 计算二进制中 1 的个数，也就是集合大小；
- 计算二进制长度（位数），减一后得到集合中最大元素的索引（注意，这里通常指的是从0开始计数的索引，如果要得到实际的元素值，则需要根据位数计算，即 2位数−1）；
- 计算二进制尾零个数，这个操作通常用于获取最低位的 1 之前的 0 的个数，但直接将其解释为集合最小元素可能不太准确，因为集合中的元素通常是从 0 或 1 开始的连续整数。不过，在某些特定场景下，这个信息可能有助于推断集合的某些性质。
调用这些函数的时间复杂度通常是 O(1)，意味着它们可以在常数时间内完成计算，不随输入规模的增长而增长。
特别地，只包含最小元素的子集，即二进制最低 11及其后面的 0，也叫 lowbit，可以用 s & -s 算出。举例说明：
s = 101100~s = 010011
(~s)+1 = 010100 // 根据补码的定义，这就是 -s => s 的最低 1 左侧取反，右侧不变
s & -s = 000100 // lowbit三、遍历集合
设元素范围从 0 到 n−1，枚举范围中的元素 i，判断 i 是否在集合 s 中。
for (int i = 0; i < n; i++) {if (((s >> i) & 1) == 1) { // i 在 s 中// 处理 i 的逻辑}
}
也可以直接遍历集合 s 中的元素：不断地计算集合最小元素、去掉最小元素，直到集合为空。
for (int t = s; t > 0; t &= t - 1) {int i = Integer.numberOfTrailingZeros(t);// 处理 i 的逻辑
}
四、枚举集合
枚举所有集合
设元素范围从 0 到 n−1，从空集 ∅ 枚举到全集 U：
for (int s = 0; s < (1 << n); s++) {// 处理 s 的逻辑
}枚举非空子集
设集合为 s，从大到小枚举 s 的所有非空子集 sub：
for (int sub = s; sub > 0; sub = (sub - 1) & s) {// 处理 sub 的逻辑
}枚举子集（包含空集）
如果要从大到小枚举 ss的所有子集 sub（从 ss枚举到空集 ∅），可以这样写：
int sub = s;
do {// 处理 sub 的逻辑sub = (sub - 1) & s;
} while (sub != s);
原理是：当 sub=0（空集）时，再减一就得到 -1，对应的二进制为 111⋯1。然后再与 s 进行按位与操作（&），就得到了 s。所以当循环到 sub=s 时，说明最后一次循环的 sub=0（空集），s 的所有子集都枚举到了，此时可以退出循环。
Gosper's Hack（枚举全集 U 的所有大小恰好为 k 的子集）
public class GospersHack { // 打印一个整数表示的子集，其中集合是 0 到 n-1 的整数 private static void printSubset(int subset, int n) { for (int i = 0; i < n; i++) { if ((subset & (1 << i)) != 0) { System.out.print(i + " "); } } System.out.println(); } // 使用 Gosper's Hack 枚举所有大小为 k 的子集 public static void enumerateSubsets(int n, int k) { // 初始子集是所有最低位的 k 个 1 int subset = (1 << k) - 1; // 循环直到达到上限（所有 n 个位中的 k 个 1 的最大子集） while (true) { // 打印当前子集 printSubset(subset, n); // 查找需要翻转的最低位的 1（即需要向右移动的最低位的 1） int x = subset & -subset; // 找到最低位的 1 int y = subset + x; // 将该位及其左边的所有位设为 1 // 清除 y 中从最低位的 1 到最右边的 1 之间的所有位 y = (y / x) >> 1; // 翻转 y 中最右边的 1 及其右边的所有位 subset = subset ^ y; // 检查是否已经生成了所有子集 if ((subset & (1 << (k - 1))) == 0) { break; } } } public static void main(String[] args) { int n = 4; // 集合大小 int k = 2; // 子集大小 enumerateSubsets(n, k); }
}这篇关于集合论与位运算之间的转换的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
