如何從1..n中得到數的xor，對於給定的n？ （例如1^2^3^...^n）？

Question

這是我遇到的面試問題，我知道如何通過重複XOR數字來獲得強力解決方案，但我不知道如何更有效地做到這一點。

我看到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的遞增值的答案時，會出現一個數學模式。它看起來像四步旋轉。這是因爲我們在xoring奇數和偶數之間來回擺動成以前偶數和奇數結果的各種組合。每個連續的異或帶給我們四分之一的旋轉。我會演示並解釋。

讓我們逐案審查這種情況下，從一開始起，n=1：

00000001 

注意，這落在解決方案，其中返回的結果是1，內case 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之後，它只會是n下一個值 - 所以getXOROne2N(4)是4

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

注意，這屬於整齊地case 0在你提出的解決方案。

現在，因爲4與前一個結果爲0是偶數，所以結果必然有一個尾隨0。因此，與xor進入折線5中的下一個值必須具有此先前位配置，但最後一位設置爲1，這意味着當我們將它與前一結果進行比較以計算getXOROne2N(5)時，我們將取消除最後一個回到1：

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

因此，我們形成我們的輪換。之後的下一個數字將輸入一個偶數並因此產生n+1（奇數），接下來的數字將取消返回到0（以偶數表示產生這個偶數結果），然後我們將得到下一個（後者必須是偶數），然後在隨後奇數的下一個值中進行變換將取消所有位，但最後一個保持打開，再次產生1。

這是一個惡性循環！但我覺得很整潔。

Answer 2

首先要注意的是，任何4個數字連續4從整除數起將導致0，如果進行了XOR：

...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