Problem: 136. 只出现一次的数字
Problem: 268. 丢失的数字

思路

异或运算是C++直接支持的运算， 写作 ^，初学C++时还会以为这是指数运算。
通常我们使用异或运算的机会比较少，然而在一些算法优化中异或的用处很大。这基于异或运算的一个性质——两个相同的数异或结果为0。
这个性质直接的使用就如 136. 只出现一次的数字 中，直接进行所有数字的异或，从而排除掉出现两次的数字。或是像 268. 丢失的数字 中，进行二次的构造，筛选掉出现过的内容。
除了这些直接的方法，还有诸如Nim博弈问题中使用异或求游戏状态的使用等，总之，关于异或，需要记住在重复出现元素时异或能帮助我们消除这一点。

复杂度

时间复杂度:

通常我们使用异或可以将空间复杂度将为$O(n)$，因为运算只需要线性的遍历。

空间复杂度:

通常我们使用异或可以将空间复杂度将为$O(1)$，因为所有运算在同一块内存上进行。

Code

136. 只出现一次的数字

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        return accumulate(nums.begin(), nums.end(), 0, bit_xor());
    }
};

---

268. 丢失的数字

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int res = 0;

        for(int i = 0; i < n; i++) {
            res = res ^ nums[i];
        }
        for(int i = 0; i <= n; i++) {
            res = res ^ i;
        }

        return res;
    }
};