算法优选：位运算实战技巧与题解

基础知识

经典例题解析

2.1 判定字符是否唯一

LeetCode 原题

算法思路： 利用【位图】的思想，每一个【比特位】代表一个【字符】，一个 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;
    }
};

2.2 消失的数字

LeetCode 原题

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

  {
:
    {
         ret = ;
         ( i : nums) ret ^= i;
         ( i = ; i <= nums.(); i++) ret ^= i;
         ret;
    }
};