02 妙用异或运算

​ 异或运算的特性十分重要 (1) x ^ 0000 = x; (2) x ^ 1111 = ~x; (3) x ^ x = 0，它的这些特性被广泛用于取返、去重等问题中。

476 数字的补数 (opens new window)

给你一个 正 整数 num ，输出它的补数。补数是对该数的二进制表示取反。

输入一个整数，输出一个整数表示原整数的补数

输入：num = 5
输出：2
解释：5 的二进制表示为 101（没有前导零位），其补数为 010。所以你需要输出 2 。

解析：

​ 看到二进制位取返就可以想到异或运算x^1111 = ~x，所以本题可以采用异或运算。本题的关键点在于怎样让参与异或运算的 1 所占位置与 num 二进制有效表示位置一致，一种方法是通过算术左移将 1 移动到有效位，同时怎么判断是否已经移到完整区间呢？可以采用与运算，如果 num 的最大有效位被覆盖，进行与运算的结果为0。

变量	二进制表示
num	00000101
mask	11111000
~mask	00000111
~mask ^ num	00000010

class Solution {
public:
    int findComplement(int num) {
        // 注意mask要用无符号，不然无法算术左移  -1 = 0xFFFFFFFF
        unsigned mask = -1; 
        while(mask & num){
            mask <<=1;
        }
        return ~mask^num;
    }
};

136 只出现一次的数字 (opens new window)

给定一个整数数组，这个数组里只有一个数字出现了一次，其余数字出现了两次，求这个只出现一次的数字。

输入是一个一维整数数组，输出是该数组内的一个整数。

输入: [4,1,2,1,2]
输出: 4

解析：

​ 本题可以利用异或运算的特性快速找出唯一出现一次的数字，应为x^x=0, x^0=x。所以在数组中出现两次的所有数字按位异或的结果是 0，出现一次的数字与0按位异或运算的结果是其本身。例如[4,1,2,1,2]，进行异或运算有4^1^2^1^2 = 4^0 = 4。

​ 这类统计频次的题使用哈希表实现也有很好的效果。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        // 将数组中所有元素逐个按位异或运算
        for(int i=0;i<nums.size();++i){
            ans = ans^nums[i];
        }
        return ans;
    }
};

268 丢失的数字 (opens new window)

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

输入一个数组，输出一个整数表示数组中没有出现的数。

输入：nums = [3,0,1] 输出：2 解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。

解析：

​ 本题是136 只出现一次的数字 (opens new window)的变种题，如果将 0 到 n 的所有数字都添加到 nums 中是不是就直接转换成了136题一样的题。例如nums = [3,0,1]，其长度为3那么添加0到3的所有元素构成nums = [3,0,1,0,1,2,3]，这样一看是不是就是找只出现一次的数字了。

​ 当然，我们不需要真的需要取重新构造 nums，在遍历 nums 时元素对应的索引就是要添加的元素。利用异或运算的特性x^x=0, x^0=x，将元素与索引进行按位异或运算最终就可以得到只出现一次的那个数了，例如3^1^0^2^1^2^3 = 2。当然，别忘了要将nums.size()这个元素加入异或运算。

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        // 将nums.size()作为第一个参与异或运算的元素，当然将它放在最后参与效果是一样的
        int ans = nums.size();
        for(int i=0;i<nums.size();++i){
            // 元素与索引进行按位异或运算
            ans ^= (nums[i]^i);
        }
        return ans;
    }
};

260 只出现一次的数字 III (opens new window)

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。

输入一个一维数组，输出一个一维数组包含只出现一次的那两个元素

输入：nums = [1,2,1,3,2,5]
输出：[3,5]
解释：[5, 3] 也是有效的答案。

解析：

​ 本题是136 只出现一次的数字 (opens new window)题的扩展，本题也可以使用异或运算解决，但是要考虑分组的情况。

​ 首先，遍历数组的所有元素，逐一进行异或运算的到只出现一次的那两个元素的异或运算结果，例如1^2^1^3^2^5 = 3^5

​ 只出现一次的那两个元素肯定不一样，所以他们的异或运算结果二进制表示中至少包含一个1。而整个数组就可以根据这个为1的二进制位进行划分，将数组中元素该位为0的划分为一组，该位为1的划分为另一组。采用这种策略就能将只出现一次的那两个元素划分到不同的组中。例如对数组1,2,1,3,2,5进行划分，3^5=(110)，根据第二位进行划分有：第一组：1(001), 1(001), 5(101)；第二组：2(010), 2(010), 3(011)

​ 然后在两组中分别进行如136 只出现一次的数字 (opens new window)题的异或运算，分别得出只出现一次的那两个元素

​ 另一个难点在于怎么找到只出现一次的那两个元素的异或运算结果中1的位置，可以采用与476 数字的补数 (opens new window)相似的方法。用mask = 0001不断的算术左移，直到mask & num != 0，那么mask中1的位置就是该划分位。

​ 根据mask划分元素也可以直接使用按位与运算，结果为0的一组，不为0的一组。

    vector<int> singleNumber(vector<int>& nums) {
        int res = 0;
        // 计算只出现一次的那两个元素的异或运算结果
        for(const auto num: nums){
            res ^= num;
        }
        // 找划分位
        int mask = 1;
        while(!(mask & res)){
            mask <<= 1;
        }
        // 分组异或运算
        int a = 0, b = 0;
        for(const auto num: nums){
            if(mask&num){
                a^=num;
            }else{
                b^=num;
            }
        }
        return vector<int>{a,b};
    }

​ 这种统计频次的题目，如果对空间复杂度没有要求的话，使用哈希表解决往往有较高的效率。

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        unordered_map<int,int> hash;
        vector<int> ans;
        for(const auto num: nums){
            if(hash.find(num) == hash.end()){
                hash[num] = 1;
            }else{
                ++hash[num];
            }
        }
        for(const auto [h_num,h_cnt]:hash){
            if(h_cnt==1){
                ans.push_back(h_num);
            }
        }
        return ans;
    }
};

693 交替位二进制数 (opens new window)

给定一个正整数，检查它的二进制表示是否总是 0、1 交替出现

输入一个整数，输出一个布尔类型表示二进制表示是否总是 0、1 交替出现

输入：n = 10
输出：true
解释：10 的二进制表示是：1010

解析：

​ 一种简单的思路是不断使用算术右移将n的二进制表示末位移出，使用按位与运算获取末位是0还是1，并且比较第 i 个和第 i-1 个末位是否相同，如果相同则直接返回false，检查完成则返回true。

class Solution {
public:
    bool hasAlternatingBits(int n) {
        // 记录第一个末位
        int pre = n & 1;
        n>>=1;
        while(n){
            // 比较第 i 个和第 i-1 个末位
            int now = n & 1;
            if(now == pre){
                return false;
            }else{
                // 更新前一个状态
                pre = now;
            }
            n >>= 1;
        }
        return true;
    }
};