用于求和异或的直接公式

Question

我必须从1到N的异或数字,是否存在直接公式？

例如,如果 N = 6那时1^2^3^4^5^6 = 7我想在不使用任何循环的情况下这样做,所以我需要一个O(1)公式(如果有的话)

Answer 1

你的公式是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. 低位是低位和下位之间的XOR.

2. 对于除低位以外的每个位,以下成立:

   • 如果N是奇数,则该位为0.
   • 如果N是偶数,那么该位等于N的对应位.

因此,对于奇数N的情况,结果总是0或1.

Answer 2

编辑
GSerg已发布没有循环的公式,但由于某种原因删除了它(现在未删除).该公式完全有效(除了一点点错误).这是类似C++的版本.

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

人们可以通过归纳证明它,检查所有分裂的提醒4.虽然,不知道如何在不产生输出和看到规律性的情况下提出它.

请多解释一下你的方法.
由于每个位在xor运算中都是独立的,因此可以单独计算它们.
此外,如果你看第k位的数字0..n,它将形成一个模式.例如,以二进制形式从0到7的数字.

000
001
010
011
100
101
110
111

你看到第k位(k从0开始),2^k有零,2^k1,然后是2^k零,等等.
因此,你可以为每个位计算有多少,而不实际经历从1到1的所有数字ñ.

例如,因为k = 2有重复的2^2 == 4零和一块.然后,

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

Answer 3

对于奇数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 4

尝试这个：

每次 N 为奇数时，LSB 就会切换，所以我们可以说

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

对于其余位可以观察到相同的模式。每次 和B（B+1从 LSB 开始）中的位N将不同时，B应设置结果中的位。

所以，最终的结果将是（包括N）：rez = N ^ (N >> 1)

编辑：抱歉，这是错误的。正确答案：

对于奇数 N：rez = (N ^ (N >> 1)) & 1

对于偶数 N：rez = (N & ~1) | ((N ^ (N >> 1)) & 1)