问题：有n个数，其中只有一个数出现一次，其他的都出现两次，求这个数（空间复杂度为常数）
/*全部xor起来即可*/
#include<cstdio>
#include<cstring>
using namespace std;
int main() {
int n,x,xor_sum=0;
scanf("%d",&n);
while(n--){
scanf("%d",&x);
xor_sum^=x;
}
printf("%d
",xor_sum);
return 0;
}
/*
1
2
3
1 3 1
5
1 2 3 2 3
*/
#include<cstdio>
#include<cstring>
using namespace std;
int main() {
int n,x,xor_sum=0;
scanf("%d",&n);
while(n--){
scanf("%d",&x);
xor_sum^=x;
}
printf("%d
",xor_sum);
return 0;
}
/*
1
2
3
1 3 1
5
1 2 3 2 3
*/
扩展：有n个数，其中只有两个数只出现一次，其他的都出现两次，求这两个数（空间复杂度为常数）
/*仿照前面的做法，得到两个数的xor，然后开个数组mp[31][31]维护每个数二进制数位上各个1的联系，最后利用这个数组将二者分离开*/
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=31;
int main(){
int mp[maxn][maxn];
memset(mp,0,sizeof(mp));
int x,xor_sum=0;
int n;
scanf("%d",&n);
while(n--){
scanf("%d",&x);
xor_sum^=x;
for(int i=0;i<maxn;i++){
if((x>>i)&1){
for(int j=0;j<maxn;j++){
if(j!=i&&((x>>j)&1)){
mp[i][j]^=1;
}
}
}
}
}
int ans=0;
for(int i=0;i<maxn;i++){
if((xor_sum>>i)&1){
ans^=(1<<i);
for(int j=0;j<maxn;j++){
if(mp[i][j]){
ans^=(1<<j);
}
}
break;
}
}
printf("%d %d
",ans,xor_sum^ans);
return 0;
}
/*
2
1 2
4
1 2 3 1
6
1 2 3 2 3 4
*/