如果[0 .. 2 64 ] 范围内的任何数字不能由给定集合中的一个或多个数字的任何XOR组合生成,那么是否存在打印至少一个无法到达的数字的有效方法,或者终止信息,没有无法访问的号码？这个问题有名字吗？它是否与另一个问题类似,或者您有任何想法,如何解决？
rap*_*sic 15
可以将每个数字视为在Z/2上的向量空间(Z/2)^ 64中的向量.你基本上想知道给定的向量是否跨越整个空间,如果没有,则生成一个没有跨越的(除了跨度总是包含零向量 - 如果你真的需要一个或多个,你将不得不特殊情况) .这可以通过高斯消除来实现.
在这个特定的向量空间中,高斯消除非常简单.从基础的空集开始.在没有更多数字之前,请执行以下操作.(1)丢弃所有零的数字.(2)扫描剩余数字的最低位(xis的最低位x & ~(x - 1)),并选择最低位设置的位.(3)把它放在基础上.(4)通过使用新的基本元素对其进行异或来更新所有其他数字.没有剩余数字具有此位或任何低位设置,因此我们在64次迭代后终止.
最后,如果有64个元素,那么子空间就是一切.否则,我们进行了少于64次迭代并跳过了一点:只打开了这个位的数字.
对于特殊情况零:当且仅当我们从不丢弃数字时(即,输入向量是独立的),零是一个选项.
4位数字的示例
从0110,0011,1001,1010开始.选择0011,因为它设置了1位.基础现在是{0011}.其他载体是{0110,1010,1010}; 注意第一个1010 = 1001 XOR 0011.
选择0110因为它设置了两位.Basis现在是{0011,0110}.其他载体是{1100,1100}.
选择1100.Basis现在是{0011,0110,1100}.其他向量是{0000}.
扔掉0000.我们完成了.我们跳过了高位,因此1000不在跨度中.