异或线性基

位运算复习¶

lowbit 函数原理

函数的功能是查找二进制意义下最低位的 1。

lowbit(x) = x & (-x)

x 在这里是正数，在计算机内采用补码存储，最高位有一个符号位 0。

-x 在计算机内采用补码存储，所以它实际上等于 x 的每一位取反，包括符号位，然后再加上 1。

补码可以拿来直接作运算。如果是正数加负数结果等于正数的情况，实际上是认为符号位上作了不进位的 mod 2 加法。另外 0 和 -0 的补码一致。

在上述规则下简单想象，即可验证正确性。

与 lowbit 相反的概念： For a positive integer x; let msb(x) be the index of the most significant bit in x.

左移位运算时容易犯蠢的地方

对于 1<<n 运算，如果说结果超出了 int，并不会自动转换成 long long 类型。这个时候就得使用 1ll<<n。

在这篇参考文献的基础上作一个展开：为什么去掉下面这个部分

C++
for (auto &b : B)
    b = min(b, b ^ x);

算法依然是对的。

Doesn’t maintain the msb condition, but still works!

msb condition 指的是，在维护基底的时候维持基底的递减顺序。

实际上不论哪种写法，关键都是从一个非 0 数变换成 0 的过程，必定是一个 msb 下降的过程。我们只需在 msb 意义下，计算出原集合内元素能使它变换成的最小值，即可决策出是把它塞进去呢，还是直接不管。

关键的待证结论

在这个算法的基础上得到的数的 msb 为 x，则不存在一种构造方法得到 msb 更小的 y。

证明的流程

验证基本事实：这个算法构造出的基底的 msb 能把后加入的消干净。

假设存在更小的 y：

它不可能是若干个 msb 和 x 的 msb 相同 1???? 得到的。排掉一个可能。
它不可能是 msb 比 x 的 msb 大的凑出来的。反之，我们可以在这些数里面取出最大的 z，考察其 msb。在假设中，我们可以让 msb 更小，于是存在一个与 z 的 msb 相同的 t。然而，z 和 t 是有先后加入基底的，这与基本事实“消干净”矛盾。

从而 y 不存在。

构造出 0，是上面 msb 变小的一个特例。于是我们验证了正确性。

A - Xor Battle (atcoder.jp) 比较神奇的是，可以证明，如果中间有一步要求在胜利集中删除元素，则会删光全部。