题意

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

请找出那个只出现一次的数字。

你可以假设满足条件的数字一定存在。

分析

统计每一位 1 的个数，如果第 k 位 1 的个数 mod 3 余 1, 那么这个只出现一次的数的第 k 位为 1, 若 1 出现的次数为 3 的倍数，则该位为 0, 这样就可以一位一位地构造出这个数。这样做要进行 32n 次操作。

class Solution {
public:
    int findNumberAppearingOnce(vector<int>& nums) {
        int res = 0;
        for(int i = 0; i < 32; i ++){
            int cnt = 0;
            for(int x : nums){
                cnt += (x >> i & 1);
            }
            if(cnt%3 == 1)res += (1 << i);
        }

        return res;
    }
};

法二：一个基于状态机的解法(有点类似于计数器)
对每一位构造二维状态，初始为 (0, 0), 遇到一个 1 转换成 (1, 0), 再遇到一个 1 转换为 (0, 1), 再遇到一个 1 转换为 (0, 0), 每种状态遇到 0 都是自环。这样每遇到 3 个 1 就会回到原点。由于位运算每位是独立的，因此 32 位可以一起算。(虽然核心想法和法1差不多，但是构造状态转移的方式真的是想不到.....)

class Solution {
public:
    int findNumberAppearingOnce(vector<int>& nums) {
        int first_pos = 0, second_pos = 0;
        for(int x : nums){
            first_pos = (first_pos ^ x) & ~second_pos;
            second_pos = (second_pos ^ x) & ~first_pos;
        }

        return first_pos;
    }
};