从1异或到N

#include <iostream>
using namespace std;
unsigned xor_n(unsigned n)
{
unsigned t = n & 3;
if (t & 1) return t / 2u ^ 1;
return t / 2u ^ n;
}
int main(int argc, char* argv[])
{
const int N = 12;
cout<<xor_n(12)<<endl;
int n = 1,sum=0;
while (n<N+1)
{
sum = sum^n;
n++;
}
cout<<sum<<endl;
return 0;
}

两种方式输出1异或到n的值

第一种方法需要做如下推导：

记 f(x, y) 为x到y的所有整数的异或值。

对 f(2^k, 2^(k+1) -1) (注意文章中的 ^ 表示的是“幂”，xor 表示“异或”，or 表示“或”)：

2^k 到 2^(k+1) -1 这2^k个数，最高位（+k位）的1个数为2^k，

若 k >= 1，则2^k为偶数，将这2^k个数的最高位(+k位)去掉，异或值不变。

因而 f(2^k, 2^(k+1) -1) = f(2^k - 2^k, 2^(k+1) -1 -2^k) = f(0, 2^k -1)

因而 f(0, 2^(k+1) -1) = f(0, 2^k -1) xor f(2^k, 2^(k+1) -1) = 0 (k >= 1)

即 f(0, 2^k - 1) = 0 (k >= 2)

对 f(0, n)  (n >= 4) 设n的最高位1是在+k位(k >= 2)，

f(0, n) = f(0, 2^k - 1) xor f(2^k, n) = f(2^k, n)

对2^k到n这n+1-2^k个数，最高位(+k位)共有 m = n+1-2^k 个1,去除最高位的1

当n为奇数时，m是偶数，因而 f(0, n) = f(2^k, n) = f(0, n - 2^k)

由于n - 2^k 与 n同奇偶，递推上面的公式，可得：f(0, n) = f(0, n % 4)

当 n % 4 == 1 时， f(0, n) = f(0, 1) = 1

当 n % 4 == 3 时， f(0, n) = f(0, 3) = 0

当n为偶数时，m是奇数，因而 f(0, n) = f(2^k, n) = f(0, n - 2^k)  or  2^k

也就是说，最高位1保持不变，由于n - 2^k 与 n同奇偶，递推上面的公式，

可得：f(0, n) = nn or  f(0, n % 4)   (nn为 n的最低2位置0)

当 n % 4 == 0 时， f(0, n) = n

当 n % 4 == 2 时， f(0, n) = nn or  3 = n + 1 （公式对 n = 2仍成立）

综上所述：

f(1, n)  =  f(0, n)  =

   n      n % 4 == 0

   1      n % 4 == 1

   n +1   n % 4 == 2

0      n % 4 == 3

最后

以上就是潇洒戒指为你收集整理的从1异或到N的全部内容，希望文章能够帮你解决从1异或到N所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。