给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

异或、位运算。

有一个简化版的题目：

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
https://leetcode.cn/problems/single-number/

一个重点：任何数字异或自己结果都是0，即x ^ x = 0
本题中，其他数字出现了 3 次。相同的 3 个数字异或的结果是数字本身，即 x ^ x ^ x = x，无法通过简单异或得出只出现一次的数字。
换种思路，如果有一个数字出现了三次，那他的二进制表示的每一位也要出现3次，如果把这些二进制表示加起来，那么每一位要么是3，要么是0。把数组中所有的数字的二进制表示都加起来，能被3整除，说明要求的数字该位上是0，不能，则

例如，[3 3 3 5]
3的二进制为: 0011，5的二进制为0101，把数组的二进制累加起来，可以得到[0 1 3 4]，根据判断，可以还原出0101。

class Solution {
public:
    //判断第index位是不是1
    bool is1(int x, int index){
        if(((x >> index) & 1) == 1) return true;
        return false;
    }

    int singleNumber(vector<int>& nums) {
        if(nums.size() == 0) return 0;
        //遍历每一位
        int base = 0;
        int res = 0;
        while(base < 32){
            int cnt = 0;
            for(auto& i : nums){
                // 对于数组中的每一个数字 判断第base位是不是1
                if(is1(i, base)){
                    cnt++;
                }
            }
            if(cnt % 3 == 1){ //说明要求的那个数，在这个位上是1
                // 移位构造res
                res = res | (1 << base);
            }
            base++;
        }
        return res;
    }
};

剑指offer中还有另外一题，求的是数组中只出现一次的两个数字。

给你一个整数数组 nums ，除 2个数字外，其余每个元素都恰出现2次 。请你找出并返回那两个只出现了一次的元素。

思路：

• 把所有数字异或，最终的结果就是那两个出现一次的数字a,b异或的结果。
• 把a^b的结果记为x，因为a和b必然不等，所以x肯定不是0。那么可以找出x的二进制表示中为1的某位。
• 基于这个位，可以将原数组分堆，数字相同的肯定分到同一堆。而要找的两个不同的数字，肯定分到了不同堆里。
• 最后两堆数组分别异或。得到的两个结果就是要找的两个数。