算法：位运算技巧与经典题目解析

前置知识

经典题目解析

判定字符是否唯一

算法思路：

利用【位图】的思想，每一个【比特位】代表一个【字符】，一个 int 类型的变量的 32 位足够表示所有的小写字母。比特位里若为 0，表示这个字符没有出现过；若为 1，表示该字符出现过。 可以用一个【整数】来充当【哈希表】。

class Solution {
public:
    bool isUnique(string astr) {
        // 利用鸽巢原理优化
        if (astr.size() > 26) return false;
        int bitmap = 0;
        for (auto i : astr) {
            int e = i - 'a';
            // 先判断字符是否出现过
            if (((bitmap >> e) & 1) == 1) return false;
            // 把当前字符加入到位图中
            bitmap |= 1 << e;
        }
        return true;
    }
};

消失的数字

算法思路：

设数组的大小为 n，则之前的数组就是 [0, n]，数组中是 [0, n] 中缺失一个数形成的序列。若，我们把数组中的所有数，以及 [0, n] 中的所有数全部【异或】在一起，那么根据【异或】运算的【抵消规则】，最终的异或结果就是缺失的数字。

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int ret = 0;
        for (auto i : nums) ret ^= i;
        for (int i = 0; i <= nums.size(); i++) ret ^= i;
        return ret;
    }
};

两整数之和

算法思路：

● 异或 ^ 运算本质是【无进位加法】； ● 按位与 & 操作能够得到【进位】； ● 然后一直循环进行，直到【进位】变成 0 为止。

class Solution {
public:
    int getSum(int a, int b) {
        while (b) {
            int x = a ^ b; // 无进位相加的结果
            // 排除 -1 的情况
            unsigned int carry = (unsigned int)(a & b) << 1; // 进位
            a = x;
            b = carry;
        }
        return a;
    }
};

只出现一次的数字 II

算法思路：

设要找的数为 ret。由于整个数组中，需要找的元素只出现了【一次】，其余的数都出现了【三次】，因此我们可以根据所有数的【某一个比特位】的总和 % 3 的结果，快速定位到 ret 的【一个比特位】上的值是 0 还是 1。 这样，我们通过 ret 的每一位比特位上的值，就可以将 ret 给还原出来。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        for (int i = 0; i < 32; i++) { // 依次修改 ret 中的每一位
            int sum = 0;
            for (auto x : nums) // 计算 nums 中所有第 i 位的和
                if (x & (1 << i)) sum++;
            sum %= 3;
            if (sum & 1) ret |= 1 << i;
        }
        return ret;
    }
};

只出现一次的数字 III

算法思路：

1. 将所有数异或在一起，由于只有两个数出现一次，其余都出现两次。所以最后的结果为 a^b。
2. a 和 b 不相等，因此 a 和 b 的二进制一定有至少一位不相同。

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        // 1. 将所有的数异或在一起
        int tmp = 0;
        for (auto x : nums) tmp ^= x;
        
        // 2. 找出 a，b 中比特位不同的那一位
        int diff = 0;
        while (true) {
            if (((tmp >> diff) & 1) == 1) break;
            else diff++;
        }
        
        // 3. 根据 diff 位的不同，将所有数划分成两类
        int a = 0, b = 0;
        for (auto x : nums) {
            if ((1 & (x >> diff)) == 1) b ^= x;
            else a ^= x;
        }
        return {a, b};
    }
};

消失的两个数字

本题就是【消失的数字】+【只出现一次的数字 III】组合起来的题。 现将数组中的数和 [1, n+2] 区间内的所有数【异或】在一起，问题就变成了：有两个数出现了【一次】，其余所有的数出现了【两次】。进而变成了【只出现一次的数字 III】这道题。

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        // 1. 将所有的数异或在一起
        int tmp = 0;
        for (auto x : nums) tmp ^= x;
        for (int i = 1; i <= nums.size() + 2; i++) tmp ^= i;
        
        // 2. 找出 a，b 中比特位不同的那一位
        int diff = 0;
        while (true) {
            if (((tmp >> diff) & 1) == 1) break;
            else diff++;
        }
        
        // 3. 根据 diff 位的不同，将所有数划分成两类
        int a = 0, b = 0;
        for (auto x : nums) {
            if ((1 & (x >> diff)) == 1) b ^= x;
            else a ^= x;
        }
        for (int i = 1; i <= nums.size() + 2; i++) {
            if ((1 & (i >> diff)) == 1) b ^= i;
            else a ^= i;
        }
        return {a, b};
    }
};