1.异或:
相同为0
不同为1
2.异或定理
\[4i \oplus (4i + 1) \oplus (4i + 2) \oplus (4i + 3) = 0 \]证明:
由于异或按位进行操作,将\(4i\)、\(4i+1\)、\(4i+2\)、\(4i+3\)二进制右移两位之后,得到\(4\)个偶数,其数值都为\(i\),因此,右移之后的异或和为\(0\)。
对于右移后的低位,其二进制异或为:
因此,上式成立。
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 $。