如果 [0 .. 264] 范围内的任何数字不能通过给定集合中的一个或多个数字的任何异或组合生成，是否有一种有效的方法可以打印至少一个无法到达的号码，或以信息终止，即没有无法到达的号码？ 这个问题有名字吗？它是否与另一个问题相似，或者您有任何想法，如何解决它？
最佳答案
在 Z/2 上的向量空间 (Z/2)^64 中，每个数字都可以视为一个向量。你基本上想知道给定的向量是否跨越整个空间，如果不是，则生成一个未跨越的向量(除了跨度总是包含零向量——如果你真的想要一个或多个，你必须特殊情况) .这可以通过高斯消元来完成。
在这个特定的向量空间上，高斯消元法非常简单。从一个空集开始作为基础。执行以下操作，直到没有更多数字为止。 (1) 丢弃所有为零的数字。 (2) 扫描剩余数的最低位集合(x 的最低位是x & ~(x - 1))并选择最低位集合的一个. (3) 放在基础上。 (4) 通过与新的基本元素进行异或运算，更新具有相同位集的所有其他数字。没有剩余数字设置了该位或任何低阶位，因此我们在 64 次迭代后终止。
最后，如果有64个元素，那么子空间就是一切。否则，我们的迭代次数少于 64 次并跳过了一点:只有这一点的数字没有被跨越。
对于零的特殊情况:当且仅当我们从不丢弃数字(即输入向量是独立的)时，零才是一个选项。
超过 4 位数的示例
从 0110、0011、1001、1010 开始。选择 0011，因为它设置了个位。基础现在是{0011}。其他向量是{0110, 1010, 1010}；注意第一个 1010 = 1001 XOR 0011。
选择 0110 因为它设置了二进制位。基础现在是 {0011, 0110}。其他向量是 {1100, 1100}。
选择 1100。基础现在是 {0011, 0110, 1100}。其他向量是 {0000}。
扔掉 0000。我们完成了。我们跳过了高位，因此 1000 不在范围内。
关于algorithm - 获取一个数字的有效方法，该数字不能从任何 XORing 组合生成，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9610355/