直接公式总结XOR [英] Direct formula for summing XOR

问题描述

我不得不从1 XOR数为N，确实存在一个直接的公式呢？

I have to XOR numbers from 1 to N, does there exist a direct formula for it ?

例如，如果 N = 6 然后 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 = 7 我想要所以我需要一个O（1）的公式来做到这一点，而无需使用任何环路（如果有的话）

For example if N = 6 then 1^2^3^4^5^6 = 7 I want to do it without using any loop so I need an O(1) formula (if any)

推荐答案

您公式为 N'放大器; （N％2？0：〜0）| （（（N和2）＆GT;＆GT; 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. 低位是低位和下位之间的异或运算。

1. Low bit is XOR between low bit and next bit.

对于除低位每一位满足以下：

For each bit except low bit the following holds:

• 如果N是奇数则该位为0。
• 如果N是偶数则该位为N个对应位。

因此​​，对于奇数n中的情况下，结果始终是0或1。

Thus for the case of odd N the result is always 0 or 1.

这篇关于直接公式总结XOR的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！