LeetCode 题解
    Single Number 系列

    Single Number 系列

    本题总共有 3 题，其中的核心思想在于利用位运算来实现一个计数器使得从 0 开始计数到 K 时能够自动重置为 0，这样当我们遍历整个数组的每一个数的时候，重复出现 K 次的数字输入设计好的布尔表达式进行计算的时候会使得我们的计数位为 0，从而达到了消去重复出现的数字的效果，不为 0 的位所组成的数字即为我们要找的那个数

    bit counter 的实现步骤

    1. 确定状态机的状态个数，确定使用多少个二进制变量来表示 比如： 3 个状态（重复出现3次）我们就需要用 2 个 bit 位即 2 个变量来表示
    2. 画出真值表，得到状态转移方程 变量包括在 1 中确定的变量和每一个数的 bit 位（非1即0），状态的转移其实就是看来的数的 bit 是 1 还是 0 来进行转换，通过公式变换或者卡洛图的方式得到转移方程
    3. 根据方程实现对应代码 将方程转化为布尔代数式

    在拥有2次重复数字的数组中寻找唯一不重复的数

    可以较为取巧地利用异或运算的特性，A XOR A = 0，B XOR 0 = B 来解决

    int singleNumber(vector<int>& nums) {
    int res=0;
    for(int i=0;i<nums.size();++i)
        res^=nums[i];
    return res;
}

    在拥有3次重复数字的数组中寻找唯一不重复的数

    第一次未化简的布尔表达式

    int singleNumber(vector<int>& nums) {
    int a=0;
    int b=0;
    for(int c : nums) {
        int tmp=(b&c) | ((~c)&a);
        b=(b&(~c)) | ((~a)&(~b)&c);
        a=tmp;
    }

    return b;
}

    已化简的布尔表达式

    int singleNumber(vector<int>& nums) {
    int counterOne = 0;
    int counterTwo = 0;
        
    for (int i = 0; i < nums.size(); i++){
        counterOne = (~counterTwo) & (counterOne ^ nums[i]);
        counterTwo = (~counterOne) & (counterTwo ^ nums[i]);
    }
    return counterOne;
}

    在拥有2次重复数字的数组中寻找唯两个无重复的数字

    第三问与第一问相比不同之处在于如果异或一遍的话得到的是两个数字的异或值，下一步要做的就是将这两个数字进行分离，通过两个数字的 diff mask 来进行异或可以满足我们的要求，两个数字的 diff 刚好就是第一问的方法得到的异或值

    vector<int> singleNumber(vector<int>& nums) {
    int ixorj=0;
    for(int n : nums)
        ixorj^=n;

	// 找到这两个数不相同的某一bit位
    int mask=1;
    while((ixorj & mask)==0) mask=mask<<1;

    int i=0;
    int j=0;
    for(int n : nums) {
		// 然后进行进一步的分离
        if (n & mask)
            i^=n;
        else
            j^=n;
    }

    return vector<int>{i, j};
}

    收获

    1. bit counter 的实现与使用 2. XOR 异或运算的威力

    #位运算

    Search in Rotated Sorted Array 旋转数组查找String to Integer (atoi) 字符串转数字