【难题+重点】剑指offer——面试题40：数组中只出现一次的数字

剑指offer——面试题40：数组中只出现一次的数字

Solution1:

书中展示了很棒的思路：
关于异或的两个性质应该知道：
(1) X^X = 0;
(2) X^0 = X;

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) { 
    //data是整型数组，num1和num2是两个只出现一次的数字
        if(data.size() < 2)
            return;
        int Res_All_XOR = 0, res_one = 0, res_two = 0;
        for(int i = 0; i < data.size(); i++)
            Res_All_XOR ^= data[i];
        int first_bit_1 = FindFirstBit1(Res_All_XOR);
        for(int i = 0; i < data.size(); i++) {
            if(IsBit1(data[i], first_bit_1))
                res_one ^= data[i];
            else 
                res_two ^= data[i];
        }
        *num1 = res_one;
        *num2 = res_two;
        return;
    }

    int FindFirstBit1(int n){ //找到第一位是1的位置
        int count = 0;
        while(n != 0) {
            if(n%2 == 1){
                count++;
                return count;
            }
            else {
                count++;
                n /= 2;
            }
        }
        return 0;
    }

    bool IsBit1(int n, int k){ //判断n的第k位是否是1，true or false
        int temp = n >> (k-1);
        if(temp%2 == 1)
            return true;
        else 
            return false;
    }
};