/*
acwing 74等价于leetcode 137
思路1：
枚举每一位
二进制第i位，模三余1则ans该位为1，模三余0则ans该位为0
思路2：有限状态机
*/
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0, cnt;
        for (int i = 0; i < 32; i ++) {
            cnt = 0; // 该位是1的出现次数
            for (auto x:nums)
                if (x >> i & 1) cnt ++;
            if (cnt % 3) ans |= 1 << i;
        }
        return ans;
    }
};
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int a = 0, b = 0;
        for (auto x:nums) {
            a = ~b & x^a; // 低位
            b = ~a & x^b; // 高位
        }
        return a;
    }
};