标签：dots 右移 异或 4k 4i 一些 oplus 性质

1.异或：

相同为0
不同为1

\[0 \oplus n = n \]

\[n \oplus n = 0 \]

2.异或定理

\[4i \oplus (4i + 1) \oplus (4i + 2) \oplus (4i + 3) = 0 \]

证明：
由于异或按位进行操作，将\(4i\)、\(4i+1\)、\(4i+2\)、\(4i+3\)二进制右移两位之后，得到\(4\)个偶数，其数值都为\(i\)，因此，右移之后的异或和为\(0\)。
对于右移后的低位，其二进制异或为：

\[00 \oplus 01 = 01 \]

\[01 \oplus 10 = 11 \]

\[11 \oplus 11 = 00 \]

因此，上式成立。

3.\(0\)到\(n\)的异或和

记\(f(n)\)为\(0\)到\(n\)的异或和，即：

\[f(n) = 0\oplus 1 \oplus 2 \oplus \dots \oplus (n - 1) \oplus n \\ \]

\[f(n)= \begin{cases} n,&n = 4k\\[2ex] 1,&n = 4k+1\\[2ex] n + 1,&n = 4k+2\\[2ex] 0,&n = 4k+3 \end{cases} \]

证明：
\(0、1、2、3\)的异或和为\(0\)，因此当\(n=4k+3\)，即有\(4\)的倍数个数字时其异或和为\(0\)。
当\(n=4k+2\)，$f(n) = (n - 2) \oplus (n - 1) \oplus n $，将其右移两位之后，得到\(3\)个为\(k\)的数字，其异或和为\(k\)，左移两位为\(4k\)。而\(00\oplus01\oplus10 = 11\)，因此，异或和为\(f(n)=4k+3 = n + 1\)
。
当\(n=4k+1\)时，$f(n) = (n - 1) \oplus n $，将其右移两位之后，得到\(2\)个为\(k\)的数字，其异或和为\(0\)，因此，异或和为\(f(n)=0+ 1= 1\)。
当\(n=4k\)时，$f(n) = n $。

4.\(a\) 到\(a+n\)的异或和

\[\begin{aligned} f(a,n) &= a \oplus (a + 1) \oplus (a + 2) \oplus \dots \oplus(a+n) \\ &=(0\oplus0)\oplus (1\oplus1)\oplus \dots \oplus((a-1) \oplus (a-1)) \oplus a \oplus (a + 1) \oplus (a + 2) \oplus \dots \oplus(a+n)\\ &= (0\oplus 1 \oplus 2 \oplus \dots \oplus (a+n) )\oplus (0\oplus 1 \oplus 2 \oplus \dots \oplus (a-1))\\ &= f(a+n) \oplus f(a-1) \end{aligned} \]

标签：dots,右移,异或,4k,4i,一些,oplus,性质
From： https://www.cnblogs.com/ymh126/p/18398684