题目：

1、给定一数组，数组中的数字均为int类型，除了一个数出现一次，其他都出现了两次，请找出这个数；

2、给定一数组，数组中的数字均为int类型，除了一个数出现一次，其他都出现了三次，请找出这个数；

思路：

这两道题，最容易想到的方法就是通过hashmap统计或者先排序后遍历的方法，但它们要么需要的空间复杂度高，要么时间复杂度高。

有没有一种方法，空间复杂度为常数，时间复杂度为O(n)？

其实两道题都可以通过位运算的简单方法来得到结果。

题目1：

相同的数异或等于0，因此将数组中所有的数全部进行异或操作，那么得到就是不重复出现的那个数。

这个思想可以应用于：一个数出现一次，其他都出现了偶数次。

题目2：

方法1：

创建一个长度为sizeof(int) 的数组count[sizeof(int)]，count[i] 表示在在i 位出现的1 的次数。如果count[i] 是3 的整数倍，则忽略；否则就把该位取出来组成答案。

方法2：

用one 记录到当前处理的元素为止，二进制1 出现“1 次”（mod 3 之后的1）的有哪些二进制位；用two 记录到当前计算的变量为止，二进制1 出现“2 次”（mod 3 之后的2）的有哪些二进制位。当one 和two 中的某一位同时为1 时表示该二进制位上1 出现了3 次，此时需要清零。即用二进制模拟三进制运算。最终one 记录的是最终结果。

代码：

题目1：

int singleNumberI(int* A,int n){    int single=0;    for(int i=0;i

题目2：

int singleNumberIII(int* A,int n){    const int NUM=32;    int count[NUM];    //fill_n(&count[0],NUM,0);    memset(count,0,NUM*sizeof(int));    for(int i=0;i
     
      >j)&1);            count[j]%=3;        }    }    int result=0;    for(int i=0;i
     

总的代码：

#include 
     
      #include 
      
       using namespace std;int singleNumberI(int* A,int n){    int single=0;    for(int i=0;i
       
        >j)&1);            count[j]%=3;        }    }    int result=0;    for(int i=0;i