algorithm - 对于给定的 n，如何从 1..n 中取数字的异或？ (例如 1^2^3^...^n)？

Question

这是我遇到的一个面试问题，我知道如何通过重复异或数字来得到暴力解决方案，但我不知道如何更有效地做到这一点。

我在 careercup 上看到了这个解决方案:

typedef unsigned long long UINT64;

UINT64 getXOROne2N(UINT64 n) {
    switch (n % 4) {
        case 0: return n;
        case 1: return 1;
        case 2: return n + 1;
        case 3: return 0;
    }
    return 0;
}

但即使听了这家伙的解释，我也不完全理解这里的逻辑，有人可以解释一下如何做到这一点吗？

Answer 1

当您查看 n 升序值的答案时，会出现一种数学模式。它看起来有点像四步旋转。这是因为我们在将奇数和偶数异或为先前偶数和奇数结果的各种组合之间来回摇摆。每个连续的异或运算都会让我们进行四分之一的循环。我将演示和解释。

让我们逐个分析，从头开始，n=1:

00000001

请注意，这属于解决方案中的 case 1，返回的结果为 1。还要注意 n 的值是奇数，因此它必然以1。

现在，当我们计算 n=2 的解时，它将是先前答案的解与 n 的新值异或:

00000001
       ^
00000010
--------
00000011

请注意，这属于解决方案的案例 2，其中返回的结果是 n + 1。另请注意，在这种情况下，n 是偶数，必然以 0 结尾——所以当异或到 1(奇数)的先前结果时，我们只是翻转额外的位, 因此在任何类似情况下的结果同样总是 n+1

对于下一个值，自然getXOROne2N(3)的结果就是之前的结果，被3异或。有趣的是，这将我们清零:

00000011
       ^
00000011
--------
00000000

当我们考虑时，这是有道理的； getXOROne2N(2) 的结果是 n+1 = 2+1 = 3，所以当我们异或到下一个值(n+ 1) 会将所有带符号的位取消为 0。另请注意，这属于您提供的解决方案中的案例 3。

现在，任何时候我们在得到 0 之后计算下一个 getXOROne2N 值，它就是 n 的下一个值 -- 所以 getXOROne2N(4 ) 为 4。

00000000
       ^
00000100
--------
00000100

请注意，这完全属于您提供的解决方案中的 case 0。

现在，因为异或到 0 的前一个结果的 4 是偶数，结果必然有一个尾随 0。因此要异或到折叠中的下一个值 5 必须有这个先前的位配置，但最后一位设置为 1，这意味着当我们将其异或到先前的结果以计算 getXOROne2N(5) 时，我们将取消除最后一位之外的所有内容并返回到 1 :

00000100
       ^
00000101
--------
00000001

这样我们就形成了轮换。在此之后的下一个将异或一个偶数，从而产生 n+1(奇数)，然后下一个将取消返回到 0(异或一个奇数number 来产生这个偶数结果)，然后我们将得到下一个 n (它必须是偶数)，然后在随后的奇数下一个值中进行异或运算将抵消除最后一个以外的所有位它仍然存在，再次产生 1。

这是一个恶性循环!但我认为非常整洁。