Polo the Penguin and XOR operation(位运算 思维)
Polo the Penguin and XOR operation
Little penguin Polo likes permutations. But most of all he likes permutations of integers from 0 to n, inclusive.
For permutation p = p0, p1, ..., pn, Polo has defined its beauty — number .
Expression means applying the operation of bitwise excluding "OR" to numbers xand y. This operation exists in all modern programming languages, for example, in language C++ and Java it is represented as "^" and in Pascal — as "xor".
Help him find among all permutations of integers from 0 to n the permutation with the maximum beauty.
Input
The single line contains a positive integer n (1 ≤ n ≤ 106).
Output
In the first line print integer m the maximum possible beauty. In the second line print any permutation of integers from 0 to n with the beauty equal to m.
If there are several suitable permutations, you are allowed to print any of them.
Examples
4
20
0 2 1 4 3
题意：给定一个 n (1 <= n <= 10^6)，求(0 ^ p0) + (1 ^ p1) + (2 ^ p2) +…… + (n ^ pn) 的最大值，其中p0 ~ pn为 0 ~ n 中的数，且每个数只利用一次。
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<algorithm>
6 using namespace std;
7 const int maxn=1e6+10;
8 int n,ans[maxn];
9 int main()
10 {
11 scanf("%d",&n);
12 memset(ans,-1,sizeof(ans));
13 for(int i=n;i>=0;i--)
14 {
15 if(ans[i]!=-1)
16 continue;
17 int k1=log2(i)+1;//求出每个数的二进制位数 并加一位
18 int k2=(1<<k1)-1;//找到和二进制下全为1的数且位数相同。
19 //就比如说你知道了二进制下位数为三且全为1的数 111
20 //然后你求的其实就是两个位数为三的数异或为111，而且你知道了其中的一个
21 //例如6 二进制位110 就是在求110^谁=111 那么这个谁 就相当于111^110
22
23 ans[k2^i]=i;
24 ans[i]=k2^i;
25 }
26 long long sum=0;
27 for(int i=0;i<=n;i++)
28 {
29 sum+=(long long )(i^ans[i]);
30 }
31 printf("%lld
",sum);
32 for(int i=0;i<=n;i++)
33 {
34 if(i)
35 {
36 printf(" ");
37 }
38 printf("%d",ans[i]);
39 }
40 printf("
");
41 }