题目中包括三个小的问题，由简单到复杂：
1，如果只有一个出现一次，考察到异或的性质，就是如果同一个数字和自己异或的活结果为零，那么循环遍历一遍数组，将数组中的元素全部做异或运算，那么出现两次的数字全部异或掉了，得到的结果就是只出现一次的那个数字。
下面首先给这部分的程序和实例分析：
1 #include<stdio.h> 2 #include<stdlib.h> 3 int main(int argv,char* argc[]) 4 { 5 int index; 6 int res=0; 7 int arr[11]={0}; 8 for(index=0;index<11;index++) 9 { 10 scanf("%d",&arr[index]); 11 } 12 for(index=0;index<11;index++) 13 { 14 res^=arr[index]; 15 } 16 printf("这个数是%d ",res); 17 system("pause"); 18 }
2，如果有两个只出现一次的数字，设定为a,b。也是应用异或，但是数组元素全部异或的结果x=a^b，因为a,b是不相同的数字，因此x肯定不为0。对于x，从低位到高位开始，找到第一个bit位为1的位置设定为第m位，这个第m位的bit肯定来自a或者来自b，不可能同时a,b的第m位（从低到高位）都为1。这样，就可以根据这个第m位就可以把数组分为两个部分，一组为第m位为0，一组为第m位为1.这样，就把问题分解成了求两个数组中只出现一次的数字了。
下面首先给这部分的程序和实例分析：
1 #include<stdio.h> 2 int get_first_position(int num) //从低位开始找到第一个位1的bit位 3 { 4 int index=1; 5 int i=0; 6 while(i<32) 7 { 8 if((num&(1<<i))==(1<<i)) 9 break; 10 else 11 { 12 index++; 13 i++; 14 } 15 } 16 return index; 17 } 18 19 int is_bit_one(int num,int index) //判断给定的索引位置的bit位是否为1 20 { 21 num=(num>>index); 22 return num&1; 23 } 24 25 void get_two_unique_num(int *a,int n,int *num1,int *num2) 26 { 27 int exclusive_or_result=0; 28 *num1=0; 29 *num2=0; 30 for(int i=0;i<n;i++) 31 exclusive_or_result^=a[i]; 32 int index=get_first_position(exclusive_or_result); 33 for(i=0;i<n;i++) 34 if(is_bit_one(a[i],index)) 35 (*num1)^=a[i]; 36 for(i=0;i<n;i++) 37 if(!is_bit_one(a[i],index)) 38 (*num2)^=a[i]; 39 } 40 41 void main() 42 { 43 int a[]={2,2,4,4,6,6,3,5}; 44 int num1,num2; 45 get_two_unique_num(a,sizeof(a)/sizeof(int),&num1,&num2); 46 printf("%d %d ",num1,num2); 47 }
3，考虑给定数组中有三个单独出现一次的数字，这个会比有两个的稍微复杂。分步分析，设定这三个数为a,b,c:
（1）将数组中的数字全部异或，得到的结果x=a^b^c，但是x不是a，b，c中的其中一个，假设x=a，那么b^c=0说明b=c，与题目给定的条件矛盾。
(2)设定f(n)可以像2中的那样，从低位开始，找到第一个bit为1的位置，f(x^a),f(x^b),f(x^c)得到的值肯定都不为0，因为x^a,x^b,x^c本身就不为0。f(x^a)^f(x^b)^f(x^c)结果不为0。因为f(x^a)^f(x^b)的结果中可能为0，也可能有两个bit为1。如果假设f(x^c)的结果bit为1的位置与f(x^a)^f(x^b)的其中一个重合，则f(x^a)^f(x^b)^f(x^c)结果中只有1个bit为1，如果不重合的话那么有3个bit位为1。
(3)这便可以推断出f(x^a)^f(x^b)^f(x^c)中至少有一个bit位为1。假设从低位到高位的第mbit位为1.那么可以得出结论x^a,x^b,x^c中有一个或者三个的第m位为1（不可能有两个，因为有两个的话，异或的结果就为0了）。
（4）证明，x^a,x^b,x^c中只有一个第m-bit位为1.假设他们的第m位都为1，那么x的第m位为0，但是x=a^b^c其第m位肯定为1，所以假设不成立。那么相反，假设x的第m位为1，a,b,c的第m位都为0，也不成立，因为x=a^b^c。所以综上所述x^a,x^b,x^c中只有一个第m位为1。那么这个问题就好办了。根据这个第m位找到第一个只出现一次的数字。然后剩下两个就是问题2所描述的问题。下面给出代码：
1 #include<stdio.h> 2 3 int get_first_bit(int num) 4 { 5 return num&~(num-1); 6 } 7 8 void get_two_unique_num(int *a,int n,int *num1,int *num2) 9 { 10 int result_code=0; 11 for(int i=0;i<n;i++) 12 result_code^=a[i]; 13 int diff=get_first_bit(result_code); 14 *num1=0; 15 *num2=0; 16 for(i=0;i<n;i++) 17 { 18 if(a[i]&diff) 19 { 20 (*num1)^=a[i]; 21 } 22 else 23 { 24 (*num2)^=a[i]; 25 } 26 } 27 } 28 29 void get_three_unique_num(int *a,int n,int *num1,int *num2,int *num3) 30 { 31 int result_code=0; 32 for(int i=0;i<n;i++) 33 result_code^=a[i]; 34 int flag=0; 35 for(i=0;i<n;i++) 36 flag^=get_first_bit(result_code^a[i]); 37 flag=get_first_bit(flag); 38 *num1=0; 39 for(i=0;i<n;i++) 40 { 41 if(get_first_bit(result_code^a[i])==flag) 42 { 43 (*num1)^=a[i]; 44 } 45 } 46 for(i=0;i<n;i++) 47 { 48 if(a[i]==(*num1)) 49 { 50 int temp=a[i]; 51 a[i]=a[n-1]; 52 a[n-1]=temp; 53 break; 54 } 55 } 56 get_two_unique_num(a,n-1,num2,num3); 57 } 58 59 void main() 60 { 61 int a[]={2,2,4,4,6,6,3,5,7}; 62 int num1,num2,num3; 63 get_three_unique_num(a,sizeof(a)/sizeof(int),&num1,&num2,&num3); 64 printf("%d %d %d ",num1,num2,num3); 65 }