面试题56(2):数组中唯一只出现一次的数字

题目

在一个数组中除一个数字只出现一次之外，其他数字都出现了三次，请找出那个只出现一次的数字

解题思路

1. 因为一个数字出现3次，那么它的二进制表示的每一位也出现三次。如果把所有出现3次的数字的二进制表示按位分别加起来，那么每一位的和都能被3整除。
2. 这样把数组中所有数字的二进制表示的每一位加起来。如果某一位的和能被3整除，那么该位对应的二进制是0.这样被3整除后剩余的位数就是出现一次的数字的二进制表示了

代码

• 细节

1. 创建一个长度为32位的辅助数组bitSum存储二进制表示的每一位的和，
   数组中每一位的和如下所示。这是第一个for循环的作用
   31 30 29 28 27 26 25........
   | 7 | 4 | 3 | 0 | 0 | 1 | 1 |
2. 第二个for循环就是求出现一次的数字，把bitSum中的每一位整除3的结果就是出现一次数字的二进制表示。

class Solution{
  public:
    
    int findNumsappearonce(int a[],int length)
    {
        if(a == NULL || length < 2)
        {
            return 0;
        }

        int bitSum[32];
        for(int i = 0;i < 32; ++i)
        {
            bitSum[i] = 0;
        }
        
        for(int i = 0; i < length;++i)
        {
            int result = 1;
            for(int j = 31;j>=0;j--)
            {
                int bit = a[i] & result;
                if(bit != 0)
                {
                    bitSum[j] += 1;
                    cout << " bitSum[j]:" << bitSum[j] << " j:" << j ;
                }
                result = result << 1;
            }
            cout << endl;
        }
        int result = 0;
        for(int i = 0;i<32;i++)
        {
            result = result << 1;
            result = result + bitSum[i]%3;
        }
        return result;
    }
};

完整代码见Github