【找出不同数字】
一个整型数组里除了一个或者两个或者三个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
1，如果只有一个出现一次，考察到异或的性质，就是如果同一个数字和自己异或的活结果为零，那么循环遍历一遍数组，将数组中的元素全部做异或运算，那么出现两次的数字全部异或掉了，得到的结果就是只出现一次的那个数字。
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 int get_first_position(int num) 2 {//从低位开始找到第一个位1的bit位 3 int index=1; 4 int i=0; 5 while(i<32) 6 { 7 if((num&(1<<i))==(1<<i)) 8 break; 9 else 10 { 11 index++; 12 i++; 13 } 14 } 15 return index; 16 } 17 int is_bit_one(int num,int index) 18 {//判断给定的索引位置的bit位是否为1 19 num=(num>>index); 20 return num&1; 21 } 22 void get_two_unique_num(int *a,int n,int *num1,int *num2) 23 { 24 int exclusive_or_result=0; 25 *num1=0; 26 *num2=0; 27 for(int i=0;i<n;i++) 28 exclusive_or_result^=a[i]; 29 int index=get_first_position(exclusive_or_result); 30 for(i=0;i<n;i++) 31 if(is_bit_one(a[i],index)) 32 (*num1)^=a[i]; 33 for(i=0;i<n;i++) 34 if(!is_bit_one(a[i],index)) 35 (*num2)^=a[i]; 36 } 37 void main() 38 { 39 int a[]={2,2,4,4,6,6,3,5}; 40 int num1,num2; 41 get_two_unique_num(a,sizeof(a)/sizeof(int),&num1,&num2); 42 printf("%d %d ",num1,num2); 43 }