位运算

位运算越来越多，我该怎么办？

这几天天天考神秘位运算，每次连部分分都拿不到，只能来恶补一下了。

本文中 \(x,y\) 均为二进制下的整数，\(x[n]\) 表示从低位到高位（标号从 \(0\) 开始）的第 \(n\) 位是什么。

阅读本文你可能需要基础二进制运算知识，如与、或、异或、取反、左移、右移等。

---

1. lowbit

相信学过树状数组的同学都知道，\(\text{lowbit}(x)\) 是指 \(x\) 中是 \(1\) 的位置中最低的是多少。如 \(\text{lowbit}(101)=0\)，\(\text{lowbit}(110)=1\)。

那么，我们如何快速对于一个 \(x\) 求出 \(\text{lowbit}(x)\) 呢？

一种不是很优美的做法：我们知道 x&(x-1) 相当于把 \(x\) 的最低位删除。因为 \(x-1\) 相当于把 \(x\) 的 \(\text{lowbit}\) 变成 \(0\)，然后比 \(\text{lowbit}\) 低的位全部都变成了 \(1\)。同时，利用这个方法，我们可以做到更快的数二进制位为 \(1\) 的个数，以及更快的枚举子集，这些我们再后面会讲。

然后我们再异或上 \(x\)，就是 x&(x-1)^x，这样就能够把 \(\text{lowbit}\) 腾出来了。

有一个更加优美的方法，也是更常用的做法，就是 x&(-x)，其中 -x 在二进制下的表现就相当于把 \(\text{lowbit}\) 保留，比它更高的尾数取反（特殊地，当 \(x=0\) 时，\(-x\) 也为 \(0\)），两者与起来刚好得出 \(\text{lowbit}\)。

2. 集合

对于一个二进制数 \(x\)，我们可以把所有 \(y\in x\) 的二进制称作它的子集。而 \(y\in x\) 相当于满足 \(x\&y=y\)。比如 1010 就属于 1011，1010 也就是 1011 的其中一个子集。特殊地，\(0\)，也就是空集，是所有集合的子集，同时 1111，也就是全集，是所有集合的并集。这样，我们就可以用一个 \(n\) 位二进制数表示一个有 \(n\) 个可选的不同元素的集合。

显然，与操作对应求交集，或操作对应求并集，异或操作对应在两个集合中总共只出现一次的元素，取反对应求补集等等。

那么，如果我们要对每一个集合，枚举它的子集，如何高效的枚举呢？

如果，我们只枚举有用状态，那么时间复杂度应该会很好，这里我们放到后面再讲。

下面的问题转化成了给定一个集合 \(x\)，不重不漏不错的枚举它的子集。

我们考虑按对应二进制大小从大往小枚举，假设当前枚举到 \(j\)，那么先把当前最后一位去掉，再把比这一位小的位全部解锁，也就是 x-1，但是这样后面会多出一些不属于这个集合的元素，所以 (j-1)&x，把其他的位给消掉。但是这样如果 \(j\) 是空集，就会发生奇怪的事，会一直都是 \(0\)，死循环，所以当 \(j=0\) 的时候就弹出，在后面补上一个空集的枚举即可。

for(int j=x;j;j=(j-1)&x)操作f[j];
操作f[0];

这样做为什么是对的呢？首先，因为有 &x，所以显然不会错，然后 -1 是单调减少的，&x 是不增的，所以每一次 \(j\) 肯定在减少，所以也不会重复。那么如何证明它不漏呢？枚举一遍这个过程也许就能很好地理解。

因为 \(x\) 中为 \(0\) 的位置不参与这个运算，所以我们可以不考虑。假设 \(x=11111\)，那么 \(j\) 的变化如下：

11110

11101

11100

11011

等。这样我们发现，如果忽略 \(x\) 中为 \(0\) 的位，那么每次只是 \(-1\)，枚举了所有有用状态。

---

那么我们如何证明复杂度呢？

假设 \(n\) 为可选元素个数，那么有 \(k\) 个元素的集合总共有 \(\dbinom nk\) 个，每次枚举时间是子集个数，也就是 \(2^k\)，所以总时间复杂度就是：

\[T_n=\sum_{k=0}^n\dbinom nkO(2^k) \]

先不管大 \(O\)，然后我们发现这是一个二项式定理：

\[\sum_{k=0}^n\dbinom nk2^k=\sum_{k=0}^n\dbinom nk2^k1^{n-k}=(1+2)^n=3^n \]

所以总时间复杂度是 \(O(3^n)\)。

如果你不了解二项式定理，可以看我的，当然，你不会证明复杂度丝毫不影响做题。

---

大概内容就这么多了，以后如果遇到更有趣的二进制操作会补一下。