2018-09-26 137. Single Number II

题意：给你一个vector数组，只有一个数出现一次，其余的数都出现三次，返回那个出现一次的数。要求：时间复杂度O(N)，空间复杂度O(1)。
背景知识：
异或操作规则：相同位相同元素异或后为0，相同位不同元素异或后为1.异或操作是一种叠加状态，当把元素val异或一个元素仓库set的时候，如果set中不存在val元素，那么set = A ^ 0 = A，相当于把A元素叠加到了set上；如果set中已经存在val元素，那么set = A ^ A = 0，相当于把A元素从set中移除了。
与操作规则：相同位全为1时与操作结果为1，其他情况结果为0.与操作是一种留存操作，即当且仅当执行与操作的两个元素对应位置都是1时结果才为1.
非操作规则：针对某一特定位置，1变0,0遍1.非操作是一种反转操作，A & （！A）= 0，相当于将A从set中删除。
解题思路：
使用两个集合set1，和set2，分别使用异或状态叠加到集合上，元素A第一次出现则将A叠加到set1上，第二次出现则把A从set1中删除并叠加到set2上，第三次出现则从set2中删除。
对集合中所有元素都执行上述操作，最后set2为空集，set1仅留下出现了一次的元素。
Here is some intuition to help understand this nice and concise solution:
First of all, consider the (set^val) as one of the following:

1. adding "val" to the "set" if "val" is not in the "set" => A^0 = A
2. removing "val" from the "set" if "val" is already in the "set" => A^A = 0
   Assume "ones" and "twos" to be sets that are keeping track of which numbers have appeared once and twice respectively;
   "(ones ^ A[i]) & ~twos" basically means perform the above mentioned operation if and only if A[i] is not present in the set "twos". So to write it in layman:
   IF the set "ones" does not have A[i]
   Add A[i] to the set "ones" if and only if its not there in set "twos"
   ELSE
   Remove it from the set "ones"
   So, effectively anything that appears for the first time will be in the set. Anything that appears a second time will be removed. We'll see what happens when an element appears a third time (thats handled by the set "twos").
   After this, we immediately update set "twos" as well with similar logic:
   "(twos^ A[i]) & ~ones" basically means:
   IF the set "twos" does not have A[i]
   Add A[i] to the set "twos" if and only if its not there in set "ones"
   ELSE
   Remove it from the set "twos"
   So, effectively, any number that appears a first time will be in set "ones" so it will not be added to "twos". Any number appearing a second time would have been removed from set "ones" in the previous step and will now be added to set "twos". Lastly, any number appearing a third time will simply be removed from the set "twos" and will no longer exist in either set.
   Finally, once we are done iterating over the entire list, set "twos" would be empty and set "ones" will contain the only number that appears once.

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int first = 0, second = 0;
        for(int i = 0; i < nums.size(); i++){
            first = (first ^ nums[i]) & (~second);
            second = (second ^ nums[i]) & (~first);
        }
        return first;
    }
};