位运算、状态压缩、枚举子集汇总

本文涉及知识点

证明容斥原理和证明集合枚举都用到了：二项式定理

【数学归纳法 组合数学】容斥原理

基础知识

位运算优先级

位运算的结合性都是从左到右。优先级低的先运算。

注意：不同的编译系统的实现可能不同,所以加上括号保险。就算你把运算顺序牢记于心，你的同事未必记得。

异或（xor ^ )

定义：x1⊕x2 = y,对各二进制位分别运算，如果x1和x2的某个二进制位不同（异），则y的此二进制位为1，否则为0。

性质一：

n个数的异或和（积），如果这n个数的某个二进制为1的数量是偶数，则结果的此二进制位是0(偶数个1）；否则结果的此二进制为是1(奇数个1)。现在用数学归纳发证明：

a, {1,1}和{0,0}是偶数个1，结果为0；{1,0},{0,1} 奇数个1，结果为1。

b,假设n个数符合，则n+1个数也符合。将前两个数进行异或运算就符合假设了。

推论一：

根据性质一，可得如下推论：n个数求异或积，可以任意调换数的顺序结果不变。

性质二：

0⊕ x = x

性质三：

x ⊕x = 0

性质四，异或逆运算是其本身：

x1 ⊕⊕ x2 = y ,则 y ⊕ x2 = x1

性质五：

x1 ⊕ ⊕ x2 <= x1 + x2

如果x1,x2的 所有的二进制位不同时为1,则 x1 ⊕ ⊕ x2 == x1 + x2

否则： x1 ⊕ x2 < x1 + x2

习题

n双m种筷子， 遗失一只，求遗失的一只长度。m值未知。

已知：2n-1只筷子的长度：{a1,a2⋯ a 2 n − 2 , a 2 n − 1 \cdots a_{2n-2},a_{2n-1}⋯a2n−2,a2n−1 }

思路：根据性质三，答案就是这2n-1的数的异或积。

位与(&)

定义： x1 & \And& x2 = y。对二进制位分别运算，x1和x2的某二进制位全部为1，y对应的二进制位为1；否则为0。

性质一：

n个数依次位与结果为y，如果这n个数的某二进制位全部为1,则y的对应二进制位为1，否则为0。

推论一：

根据性质一，可得如下推论：n个数求与积，可以任意调换数的顺序结果不变。

性质二：

(-1)&x = x

性质三：

x1 & x2 = y <=min(x1,x2)

位或（|）

定义： x1 ∨ x2 = y。对二进制位分别运算，x1和x2的某二进制位全部为0，y对应的二进制位为0；否则为1。

性质一：

n个数依次位与结果为y，如果这n个数的某二进制位全部为0,则y的对应二进制位为0，否则为1。

推论一：

根据性质一，可得如下推论：n个数求与积，可以任意调换数的顺序结果不变。

性质二：

0 ∨ x = x

性质三：

x1  x2 >= max(x1,x2)

取反（~）

定义：各二进制位0变1,1变0。

位左移（<<)、位右移(>>)

状态压缩

用int mask的二进制位代替一个bool数组v，此数组长度不超过31。第i位为1，表示v[i]=true；第i位为0，表示v[i]=false。

mask&(1<∈ \in∈[0,31) 最低位i是0。以下操作，只影响第i位，不影响其它位。

如果mask第i位无论是0还是1,设置为1 mask |=(1<

如果mask第i位是无论是1还是0，设置为0 mask &=~(1<

将mask的第一位取反(0变1,1变0)。 mask ^=(1 << i）

子集状态压缩(枚举子集）

从大到小枚举mask的子集，寻找下一个子集，如果sub为0,没有比它小的子集。否则从右到左寻找第一个不为0的位，假定此位是i1，将i1位减1，也就是变成0。i1后面的位取最大，也就是mask的后i1位。

sub-1 ：由于是从大到小枚举，所以(sub-1)比i1高的位和mask一致。

第i1位变成0。

比i1位低的全为1。

故：mask&(sub-1)就是 比sub小的最大子集。

注意：通过此方法枚举maxMask =(1

0被maxMask 所有子集枚举，共2ⁿ次。

常见的运算

x是正整数

(x-1)& :将最低位的1设置成0。

令第i1位是1，如果有多位是1，i1是最小的。

比i1高的位：两者完全相同，故不变。

i1位：一个为1，一个为1，故为0。

比i1低的为：一个为1,一个为0，故全为0。

(-x)&

除最低位的1外，全部置成0。

负数存储的是补码，反码+1.

令第i1位是1，如果有多位是1，i1是最小的。

比i1高的位： x和-x相反，故全为0。

i1位：x和-x都为1，故结果为1。

比i1低的位： x和-x都为0，故结果为0。

区间(子数组)位与（位或）模板

vector<int> nums;

集合s 记录所有的tr，则s的元素数量，最大31个。因为删除重复元素后，tr的二进制1至少少1个。

位或类似，每个不重复的元素至少增加一个1。

最大公约数，也是如此。每次至少除以2。

vector<vector<pair<int, int>>> vNumIndex(nums.size());
for (int i = 0; i < nums.size(); i++) {
  if (i) {
    for (const auto& [preNum, preIndex] : vNumIndex[i - 1]) {
      const int iNew = preNum | nums[i];
      if (vNumIndex[i].empty() || (vNumIndex[i].back().first != iNew)) {
        vNumIndex[i].emplace_back(make_pair(iNew, preIndex));
      }
      else {
        vNumIndex[i].back().second = preIndex;
      }
    }
  }
  if (vNumIndex[i].empty() || (vNumIndex[i].back().first != nums[i])) {
    vNumIndex[i].emplace_back(make_pair(nums[i], i));
  }
  else {
    vNumIndex[i].back().second = i;
  }
}

vNumIndex[i]记录 nums[x…i]的异或值（不重复）及索引。重复值保留索引大的。x∈ \in∈[0,x]。

第二个版本的模版

class CRangCal {
public:
  template<class _Pr, class T = int>
  static vector<vector<pair<T, int>>> RangCal(const vector<T>& nums, _Pr pr) {
    vector<vector<pair<int, int>>> vNumIndex(nums.size());
    for (int i = 0; i < nums.size(); i++) {
      if (i) {
        for (const auto& [preNum, preIndex] : vNumIndex[i - 1]) {
          auto iNew = pr(preNum, nums[i]);
          if (vNumIndex[i].empty() || (vNumIndex[i].back().first != iNew)) {
            vNumIndex[i].emplace_back(make_pair(iNew, preIndex));
          }
          else {
            vNumIndex[i].back().second = preIndex;
          }
        }
      }
      if (vNumIndex[i].empty() || (vNumIndex[i].back().first != nums[i])) {
        vNumIndex[i].emplace_back(make_pair(nums[i], i));
      }
      else {
        vNumIndex[i].back().second = i;
      }
    }
    return vNumIndex;
  }
};

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者 操作系统：win10 开发环境： VS2022 C++17

如无特殊说明，本算法用**C++**实现。