HashSet<int>方法与位运算符的逻辑映射关系问询

没错，这两者在逻辑上高度对应——本质都是对「元素存在性」的集合操作，一个是面向对象的集合API，一个是基于二进制位的底层运算。具体映射关系如下：

• 添加元素（HashSet.Add(int x)） → 按位或（|）
  向集合中添加元素x，等价于将整数的第x位设为1（重复添加无变化）。示例：

  // HashSet方式
  var set = new HashSet<int> {1,3};
  set.Add(2);
  // 位运算模拟（用int存储位状态）
  int bits = (1 << 1) | (1 << 3);
  bits |= (1 << 2);
  

• 判断元素存在（HashSet.Contains(int x)） → 按位与（&）
  检查x是否在集合中，等价于判断整数的第x位是否为1：

  bool exists = set.Contains(3);
  bool bitExists = (bits & (1 << 3)) != 0;
  

• 移除元素（HashSet.Remove(int x)） → 按位与非（& ~）
  移除集合中的x，等价于将整数的第x位设为0（元素不存在时无变化）：

  set.Remove(1);
  bits &= ~(1 << 1);
  

• 集合并集（HashSet.UnionWith(HashSet other)） → 按位或（|）
  合并两个集合的所有元素，等价于两个整数的按位或运算：

  var set1 = new HashSet<int> {1,2};
  var set2 = new HashSet<int> {2,3};
  set1.UnionWith(set2);
  int bits1 = (1<<1)|(1<<2);
  int bits2 = (1<<2)|(1<<3);
  int unionBits = bits1 | bits2;
  

• 集合交集（HashSet.IntersectWith(HashSet other)） → 按位与（&）
  保留两个集合的公共元素，等价于两个整数的按位与运算：

  set1.IntersectWith(set2);
  int intersectBits = bits1 & bits2;
  

• 集合差集（HashSet.ExceptWith(HashSet other)） → 按位与非（& ~）
  保留当前集合中不在另一个集合的元素，等价于当前位状态 & ~另一个位状态：

  set1.ExceptWith(set2);
  int exceptBits = bits1 & ~bits2;
  

• 对称差集（HashSet.SymmetricExceptWith(HashSet other)） → 按位异或（^）
  保留只在其中一个集合存在的元素，等价于两个整数的按位异或运算：

  set1.SymmetricExceptWith(set2);
  int symmetricBits = bits1 ^ bits2;
  

注意事项 #

这种映射仅适用于元素值范围较小的场景（比如元素是0_{31的int，对应32位整数；0}63对应long），因为单整数的位数有限。如果HashSet中的元素超出这个范围，就无法用单个整数的位运算模拟集合操作了。

内容的提问来源于stack exchange，提问作者JBurlison