数组中每个数重复3次只有一个例外，找出

方法一：
int类型有32位，假如二进制位不进位的话，对数组中除了single数以外的所有数做累加，32位每一位上的值都是3。假如我对每一位是做模3加法的话，把数组所有数加起来，32位每一位的值应该有1有0，因为三个相同数加起来都会模3变为0，所以剩下的1都是属于single数的，所以这个累加和就等于single数。

这个方法时间是O(32*N)，但要分别计算每一位的累加，分别作32次累加。空间是O(1)。

class Solution {
public:
    int singleNumber(int A[], int n) {
 
        int result = 0;
        int sum;
        int i, j;
        for(i=0;i<32;i++)
        {
            sum = 0;
            for(j=0;j<n;j++) sum += ((A[j]>>i)&1); //每轮只对固定某一位做累加
            
            if(sum%3 == 1)
                result = result|(1<<i);
        }
        return result;
    }
};

方法二：
方法一之所以要单独计算每一位的累加，是因为二进制位无法实现能累加到3并且还不进位。想要不进位（不进位的话才能并行着操作），我们就使用与或非位运算；想要能累加到3，我们需要自定义一些规则来实现它。

那么用与/或/非/异或来模拟实现位的模3加法。这样的加法有三个状态0、1、2，但是二进制位只有0、1两个状态，所以我需要借助一个数来作辅助。int型变量ones它的每一位的意义是，如果该位为1，则表示该位的当前累加和为1。int型变量twos它的每一位的意义是，如果该位为1，则表示该位的当前累加和为2。那么如果某一位在ones和twos都为0，说明该位的当前累加和为0。（下面制定的加法规则会让ones和twos中的某位不可能都是1）

那么加法的过程有这几种情况，对于某一位，ones和twos中的对应位如何变化：

1、加数X为0：ones不变，twos不变。

2、加数X为1：

若之前ones为1，则ones变0，twos变1。

若之前twos为1，则ones还是0，twos变0。

若之前都为0，则ones变1，twos还是0。

具体的情况如下表格：

观察上面的表格，这个过程很类似数字电子课程里面的组合逻辑电路设计。

根据规律，构造出一种运算：

ones = (~twos) & (ones ^ X); （一定注意：执行完这句之后，ones值就变成新的了！）

twos = (~ones) & (twos ^ X);

那么，出现4次也可以依此类推：

ones = (~threes) & (~twos) & (ones ^ A[i]);

twos = (~threes) & (~ones) & (twos ^ A[i]);

threes = (~twos) & (~ones) & (threes ^ A[i]);

对题目数组中所有数累加之后，必定是twos全部为0（出现两次的数），ones有1有0，此时的ones就是我们要找的single数。

方法二的时间复杂度更好，只累加一次即可。这种用位运算模拟加法的方法可以达到多个位同时相加的并行的效果。当然它的使用限制是，累加最终结果的情况是要提前知道的，这里就是知道累加最终一定是ones有1有0，twos全0，累加结果就体现在这里。

class Solution {
public:
    int singleNumber(int A[], int n) {
        int ones = 0;
        int twos = 0;
        int i;
        for(i=0;i<n;i++)
        {
            ones = (~twos) & (ones ^ A[i]);
            twos = (~ones) & (twos ^ A[i]);//注意这里用的ones是新的ones，这一点和数电不同。
        }
        return ones;
    }
};

扩展：

一个数组，一个数出现一次，另一个出现两次，其他都出现四次，找出出现一次和出现两次的数

#include <stdio.h>
int singleNumber(int A[], int n, int *two) {
    int ones = 0;
    int twos = 0;
    int threes = 0;
    int i;
    for(i=0;i<n;i++)
    {   
        ones = (~threes) & (~twos) & (ones ^ A[i]);
        twos = (~threes) & (~ones) & (twos ^ A[i]);
        threes = (~twos) & (~ones) & (threes ^ A[i]);
    }   
    *two = twos;
    return ones;
}

int main() {

    int a[] = { 10, 2, 10, 1, 10, 3, 3, 3, 3, 2, 10};
    int two;
    int one = singleNumber(a, sizeof(a)/sizeof(int), &two);
    printf("%d, %d\n", one, two); 
}
1, 2