位运算算法专题：判断字符唯一性、丢失数字与两数之和等

常见位运算总结

1 ~> 刷前必刷题单

干掉一个数（n）二进制表示中最右侧的 1：

• 191. 位 1 的个数

class Solution {
public:
    int hammingWeight(int n) {
        int count = 0;
        while (n) {
            n &= (n - 1);
            count++;
        }
        return count;
    }
};

• 338. 比特位计数

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> ans(n + 1, 0);
        for (int i = 1; i < n + 1; i++) {
            ans[i] = ans[i >> 1] + (i & 1);
        }
        return ans;
    }
};

• 461. 汉明距离

class Solution {
public:
    int hammingDistance(int x, int y) {
        int val = x ^ y;
        int count = 0;
        while (val) {
            val &= (val - 1);
            count++;
        }
        return count;
    }
};

异或（^）运算的运算律相关的算法题：

• 136. 只出现一次的数字

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int result = 0;
        int i = 0;
        while (i < nums.size()) {
            result ^= nums[i];
            i++;
        }
        return result;
    }
};

• 260. 只出现一次的数字 III

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        vector<int> ans(2, 0);
        int result = 0;
        int i = 0;
        while (i < nums.size()) {
            result ^= nums[i];
            i++;
        }
        unsigned int val = result & (-(unsigned int)result);
        i = 0;
        while (i < nums.size()) {
            if (nums[i] & val) {
                ans[0] ^= nums[i];
            } else {
                ans[1] ^= nums[i];
            }
            i++;
        }
        return ans;
    }
};

033 判断字符是否唯一

题目描述： 给定一个字符串，判断其中每个字符是否唯一。

1.1 解法（位图的思想）：

利用「位图」的思想，每一个【比特位】代表一个【字符】，一个 int 类型的变量的 32 位 足够表示所有的小写字母。比特位里面如果是 0，表示这个字符没有出现过。比特位里面的值是 1，表示该字符出现过。 那么我们就可以用一个【整数】来充当【哈希表】。

1.2 算法实现

class Solution {
public:
    bool isUnique(string astr) {
        // 利用鸽巢原理做优化
        if (astr.size() > 26) return false;
        // 搞定位图
        int bitMap = 0;
        // 遍历字符串
        for (auto ch : astr) {
            int i = ch - 'a';
            // 先把重复的字符处理一下
            if ((bitMap >> i) & 1 == 1) return false;
            // 说明字符没有出现过，添加到位图中
            bitMap |= 1 << i;
        }
        return true;
    }
};

034 丢失的数字

题目描述： 给定包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。

2.1 解法：位运算

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

2.2 算法实现

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        // 用 ret 表示确实的那个数字
        int ret = 0;
        // 把数组中的数异或在一起
        for (auto x : nums) ret ^= x;
        // 把 0~n 中的数异或在一起
        for (int i = 0; i <= nums.size(); i++) ret ^= i;
        return ret;
    }
};

035 两整数之和

题目描述： 不使用运算符 + 和 - ，计算两整数 a 、b 之和。

3.1 位运算解法的算法思路

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

3.2 算法实现

class Solution {
public:
    int getSum(int a, int b) {
        while (b != 0) { // 一直重复这个操作
            int x = a ^ b; // 先算出无进位相加的结果
            unsigned int carry = (unsigned int)(a & b) << 1; // 算出算出进位
            // 这里用 unsigned int 是考虑到 a & b 如果是 -1 的话，此时左移操作是没有定义的，用这种方式处理一下 -1 的情况（把 -1 当成无符号的整数）
            a = x; // 把无进位相加结果给 a
            b = carry; // 把进位相加结果给 b
        }
        return a;
    }
};

036 只出现一次的数字 II

题目描述： 给你一个整数数组 nums ，除某个元素仅出现一次外，其余每个元素都恰出现三次 。请你找出并返回那个只出现了一次的元素。

4.1 解法思路：比特位计数

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

4.2 算法实现

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

037 消失的两个数字

题目描述： 给定一个包含 0, 1, 2, ..., n 中 n 个数的数组 nums，找出 0..n 中没有出现在数组中的那两个数。

5.1 解法：位运算

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

5.2 算法实现

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