用於求和的直接公式XOR

Question

我必須從1到N的XOR數，它是否存在直接的公式？

例如，如果N = 6然後1^2^3^4^5^6 = 7我想這樣做，不使用任何循環，所以我需要一個O（1）式（如果有的話）

Answer 1

試試這個：

的LSB每次被觸發N是奇數，所以我們可以說

rez & 1 == (N & 1)^((N >> 1) & 1) 

對於其餘的位可以觀察到相同的模式。 每次在N中的位B和B+1（從LSB開始）將不同，應該設置結果中的位B。

所以，最終的結果將是（包括N）：rez = N^(N >> 1)

編輯：對不起，這是錯誤的。正確答案：

奇數N：rez = (N^(N >> 1)) & 1

即使N：rez = (N & ~1) | ((N^(N >> 1)) & 1)

Answer 2

編輯
GSerg已發佈沒有循環公式，但刪除了它由於某種原因（現在未刪除）。該公式是完全有效的（除了一個小錯誤）。這是類似C++的版本。

if n % 2 == 1 { 
    result = (n % 4 == 1) ? 1 : 0; 
} else { 
    result = (n % 4 == 0) ? n : n + 1; 
} 

可以通過歸納法證明，通過4檢查所有除法提醒。雖然，不知道如何在不產生輸出和看到規律的情況下提出它。

請詳細解釋一下您的方法。
由於每個位在異或運算中都是獨立的，因此可以分別計算它們。
此外，如果您查看第0..n號的第k位，它將形成一個模式。例如，以二進制形式從0到7的數字。

000 
001 
010 
011 
100 
101 
110 
111 

你看到的第k位（K從0開始），再有就是2^k零，2^k的，然後2^k零等
因此，你可以爲每個位計算有多少那些實際上沒有經歷從1到n的所有數字。

例如，對於k = 2，存在重複的2^2 == 4零和1的塊。然後，

int ones = (n/8) * 4; // full blocks 
if (n % 8 >= 4) { // consider incomplete blocks in the end 
    ones += n % 8 - 3; 
} 

Answer 3

讓我們說，異或所有的值從1到N的功能是XOR（N），然後

 
XOR(1) = 000 1 = 0 1 (The 0 is the dec of bin 000) 
XOR(2) = 001 1 = 1 1 
XOR(3) = 000 0 = 0 0 
XOR(4) = 010 0 = 2 0 
XOR(5) = 000 1 = 0 1 
XOR(6) = 011 1 = 3 1 
XOR(7) = 000 0 = 0 0 
XOR(8) = 100 0 = 4 0 
XOR(9) = 000 1 = 0 1 
XOR(10)= 101 1 = 5 1 
XOR(11)= 000 0 = 0 0 
XOR(12)= 110 0 = 6 0 

我希望你能看到的格局。它也應該與其他數字相似。

Answer 4

對於奇數N，其結果是要麼1或0（環狀，0爲N=3，1 N=5，0爲N=7等）

對於偶數N，其結果是要麼N或N+1（環狀， N + 1代表N=2，N代表N=4，N + 1代表N=6，N代表N=8等）。

僞代碼：

if (N mod 2) = 0 
    if (N mod 4) = 0 then r = N else r = N+1 
else 
    if (N mod 4) = 1 then r = 1 else r = 0 

Answer 5

你的公式是N & (N % 2 ? 0 : ~0) | (((N & 2)>>1)^(N & 1))：

int main() 
{ 
    int S = 0; 
    for (int N = 0; N < 50; ++N) { 
     S = (S^N); 
     int check = N & (N % 2 ? 0 : ~0) | (((N & 2)>>1)^(N & 1)); 
     std::cout << "N = " << N << ": " << S << ", " << check << std::endl; 
     if (check != S) throw; 
    } 

    return 0; 
} 

輸出：

N = 0: 0, 0    N = 1: 1, 1    N = 2: 3, 3 
N = 3: 0, 0    N = 4: 4, 4    N = 5: 1, 1 
N = 6: 7, 7    N = 7: 0, 0    N = 8: 8, 8 
N = 9: 1, 1    N = 10: 11, 11   N = 11: 0, 0 
N = 12: 12, 12   N = 13: 1, 1   N = 14: 15, 15 
N = 15: 0, 0   N = 16: 16, 16   N = 17: 1, 1 
N = 18: 19, 19   N = 19: 0, 0   N = 20: 20, 20 
N = 21: 1, 1   N = 22: 23, 23   N = 23: 0, 0 
N = 24: 24, 24   N = 25: 1, 1   N = 26: 27, 27 
N = 27: 0, 0   N = 28: 28, 28   N = 29: 1, 1 
N = 30: 31, 31   N = 31: 0, 0   N = 32: 32, 32 
N = 33: 1, 1   N = 34: 35, 35   N = 35: 0, 0 
N = 36: 36, 36   N = 37: 1, 1   N = 38: 39, 39 
N = 39: 0, 0   N = 40: 40, 40   N = 41: 1, 1 
N = 42: 43, 43   N = 43: 0, 0   N = 44: 44, 44 
N = 45: 1, 1   N = 46: 47, 47   N = 47: 0, 0 
N = 48: 48, 48   N = 49: 1, 1   N = 50: 51, 51 

說明：

1. 低位是低位和下一位之間的異或。

2. 對於除低比特的每個比特下式成立：

   • 如果N爲奇數則該位爲0
   • 如果N爲偶數則該比特等於N.
   的比特相對應

因此，對於奇數n中的情況下，結果始終是0或1。

Answer 6

大answe通過Alexey Malistov！他公式的變體：n & 1 ? (n & 2) >> 1^1 : n | (n & 2) >> 1或等效n & 1 ? !(n & 2) : n | (n & 2) >> 1。

Answer 7

這種方法避免了使用條件語句F(N)=(N&((N&1)-1))|((N&1)^((N&3)>>1)

F(N)= (N&(b0-1)) | (b0^b1) 

如果你看第幾號的XOR你：

N  | F(N) 
------+------ 
0001 | 0001 
0010 | 0011 
0011 | 0000 
0100 | 0100 
0101 | 0001 
0110 | 0111 
0111 | 0000 
1000 | 1000 
1001 | 0001 

希望你注意到模式：

如果N mod 4 = 1比F(N)=1
如果N mod 4 = 3比F(N)=0
如果N mod 4 = 0比F(N)=N
如果N mod 4 = 2比F(N)=N但與第一位爲1所以N|1

棘手的部分是沒有條件語句得到這個在一個聲明中生病解釋我使用的邏輯去做這個。

取N個第2顯著位叫他們：

b0和b1和這些與獲得：

b0 = N&1 
b1 = N&3>>1 

注意，如果b0 == 1我們必須0所有位，但如果除了第一位保持不變之外，並不是所有的位。

N & (b0-1)：我們可以做到這一點的行爲這工作，因爲2的補，-1等於設置爲1所有位的數量和1-1=0所以當b0=1這導致F(N)=0 ..所以這是第一部分功能：

F(N)= (N&(b0-1))... 

現在這會爲工作了N mod 4 == 3和0，對另2例完全可以在b1，b0和F(N)0看：

b0|b1|F(N)0 
--+--+----- 
1| 1| 0 
0| 0| 0 
1| 0| 1 
0| 1| 1 

好的，希望這張真相表看起來很熟悉！它是b0 XOR b1 (b1^b0)。所以現在我們知道如何獲得最後一位讓把那我們的功能：

F(N)=(N&(b0-1))|b0^b1 

和你去那裏，一個功能，而無需使用條件語句。如果要計算從正數a到b的XOR，這也很有用。你可以這樣做： F(a) XOR F(b)。

Answer 8

看看這個。這將解決您的問題。

https://stackoverflow.com/a/10670524/4973570

從1計算XOR總和N：

int ans,mod=N%4; 
if(mod==0) ans=N; 
else if(mod==1) ans=1; 
else if(mod==2) ans=N+1; 
else if(mod==3) ans=0; 

Answer 9

用最小的變化原來的邏輯：

int xor = 0; 
for (int i = 1; i <= N; i++) { 
    xor ^= i; 
} 

我們可以有：

int xor = 0; 
for (int i = N - (N % 4); i <= N; i++) { 
    xor ^= i; 
} 

它有一個循環，但需要一段時間才能執行。我們遍歷for循環的次數在1和4之間變化。

Answer 10

這個怎麼樣？

!(n&1)*n+(n%4&n%4<3) 

Answer 11

如果仍然有人需要在這裏簡單的Python的解決方案：

def XorSum(L): 
    res = 0   
    if (L-1)%4 == 0: 
     res = L-1 
    elif (L-1)%4 == 1: 
     res = 1 
    elif (L-1)%4 == 2: 
     res = (L-1)^1 
    else: #3 
     res= 0 
    return res 

Answer 12

這工作沒有任何n任何問題的罰款;

int xorn(int n) 
{ 

    if (n % 4 == 0) 
     return n; 
    else if(n % 4 == 1) 
     return 1; 
    else if(n % 4 == 2) 
     return n+1; 
    else 
     return 0; 
}