1

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

我在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;
}

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

4

2 回答 2

3

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

让我们从头开始逐案检查n=1：

00000001

请注意，这属于case 1解决方案，其中返回的结果是 1。还要注意，这个值n是奇数，所以它必然以 . 结尾1。

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

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

请注意，这属于case 2解决方案，返回的结果是n + 1. 另请注意，在这种情况下n是偶数，必然以0-- 结尾，因此当与前一个结果 1（奇数）异或时，我们只会翻转额外的位，因此任何类似情况下的结果同样总是n+1

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

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

当我们考虑它时，这是有道理的。结果getXOROne2N(2)是n+1 = 2+1 = 3，所以很自然地，当我们将沿 ( ) 的下一个值异或时n+1，它将取消所有有符号位回到 0。另请注意，这属于case 3您提出的解决方案。

现在，getXOROne2N只要我们在得到 0 之后计算下一个值，它就只是下一个值——4 也是n如此getXOROne2N(4)。

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

请注意，这完全符合case 0您提出的解决方案。

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

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

因此我们形成了我们的旋转。这之后的下一个将异或一个偶数并因此产生n+1（奇数），然后下一个将取消0（异或一个奇数以产生这个偶数结果），然后我们将得到下一个n（它必须是偶数），因此在随后的奇数下一个值中进行异或运算将抵消除最后一个保持打开的所有位，再次产生 1。

这是一个恶性循环！但我认为相当整洁。

于 2015-11-14T07:13:05.313 回答
2

首先要注意的是，如果 XORed，从可被 4 整除的数字开始的连续 4 个数字将导致 0：

    ...00 - starting with any binary digits
    ...01
    ...10
    ...11
XOR -----
        0 : 4 times (...), twice 1 for both lower digits

这实际上意味着只有在最大可被 4 整除之后的最后一个数字才会n形成实际结果（您可以将之前的所有数字分组为四边形，每个数字都为 0）。

所以，它来了

%4    n               calc           result
0   ...00  ->  ...00 =               n
1   ...01  ->  ...00 XOR ...01 =     1
2   ...10  ->  ...10 XOR 1 = ...11 = n + 1
3   ...11  ->  ...11 XOR ...11 =     0
于 2015-11-14T07:14:25.653 回答