位运算

Single Number ：　　一个整数数列，除其中一个数以外，其他数都出现2次；试找出这个数 

要求线性复杂度，且不用什么额外空间。

解题思路：

寻找一种位运算^[1]，满足结合律、交换律，且2个相同的数做该运算会得到单位元。

很容易想到位运算 同或，异或。以异或为例，

0^1 = 1,

0^0 = 0,

1^1 = 0.

0为单位元。满足交换律，结合律。

所有出现两次的数做按位异或运算得到0 （00000...），单位元0再与只出现一次的数运算，得到的结果还是这个数。

Single Number II：　　一个整数数列，除其中一个数以外，其他数都出现3次；试找出这个数 

要求线性复杂度，且不用什么额外空间。

解题思路：

寻找一种位运算，满足结合律、交换律，且3个相同的数做该运算会得到单位元。

试遍了8种 (要满足交换律)从{0,1} ->{0,1} 的位运算，根本不能。有时候思路难免过于局限。

这种运算是什么呢?  add bit by bit but mod 3.

int singleNumber(int A[], int n) {
    
    int carrier = 0, sum = 0,oneBits;
    int i = 0;
    for (;i< n;i++)
    {
        carrier += sum&A[i];
        sum ^= A[i];
        
        oneBits = carrier&sum;
        
        carrier ^= oneBits;
        sum ^= oneBits;
    }
    
    return (carrier<<1) + sum;
        
}

[1]位运算：因为最后要恢复只出现一次的那个数，按位运算可以保证维度。

题目来源：

https://leetcode.com/problems/single-number/ 

https://leetcode.com/problems/single-number-ii/