哈理工oj 1128find them解题报告

链接：http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1128

看很多人的博客都没有位运算这一个专题分类，可能觉得没必要单独分类吧，但是我还是觉得有这个必要对几种位运算做一次深入探讨

这道题是说，有一组数，共有偶数个数，这些数当中有一部分数出现了偶数次，有两个数出现了奇数次，要找出这两个数

这道题涉及到的位运算是异或即^，对于^运算，满足交换律，而且满足a^a=0，且0^a=a,a^b=c则a^c=b这是这道题用到的主要性质，而且我么知道，如果两个二进制数不相等，那么起码有一位一个为0，一个为1，这也是我们要利用的地方，首先所有出现偶数次的数异或之后都变成了0，那么所有数的异或也就是出现奇数次的那两个数的异或了，然后我们再根据他们不同的那一位对整个数组分类，再异或回去，如果出现奇数次的两个数为a何b，那么n=a^b;我们最后找到的是a^n=b，那么a=b^n;得出结果

View Code

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 
 5 int a[100001];
 6 
 7 int main()
 8 {
 9     int n,num,j;
10     unsigned int i;
11     while(scanf("%d",&n)!=EOF)
12     {
13         num=0;
14         for(i=1;i<=n;i++)
15         {
16             scanf("%d",&a[i]);
17             num^=a[i];
18         }
19         int n1=num;
20         for(i=1;;i*=2)
21         {
22             if(i&num)
23                 break;
24         }
25         num=0;
26         for(j=1;j<=n;j++)
27             if(i&a[j])
28                 num^=a[j];
29         n1^=num;
30         if(n1>num)
31         {
32             int temp;
33             temp=n1;
34             n1=num;
35             num=temp;
36         }
37         printf("%d %d\n",n1,num);
38     }
39     return 0;
40 }