位运算实战：判断字符唯一、丢失的数字、两整数之和等

异或运算天然支持'消消乐'（同一个数异或两次就抵消），它经常用来处理'只有一个数出现一次，其他都出现两次'这类问题。下面的两个题就是典型，其中第二个还延伸出分组异或的技巧。

• 136. 只出现一次的数字

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int result = 0;
        for (int num : nums) {
            result ^= num;
        }
        return result;
    }
};

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

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

判断字符是否唯一

这道题可以用位图的思想：一个 int 有 32 位，足以表示所有小写字母。每一位代表一个字符是否出现过（0 未出现，1 已出现）。遍历字符串时，先检查对应位是否为 1，是则重复返回 false；否则将该位置 1。为了让位运算更紧凑，可以先利用鸽巢原理：字符串长度 > 26 直接返回 false。

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;
    }
};

丢失的数字

数组大小为 n，原数字范围是 [0, n]，现在缺失一个数。如果我们将数组中的每个数和 [0, n] 的每个数全部异或在一起，根据异或的消消乐性质，成对的数会抵消，最后剩下的就是缺失的那个数。

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

两整数之和

不能使用加号时，可以用位运算模拟加法。异或 ^ 相当于无进位加法，按位与 & 再左移一位得到进位。反复将无进位和与进位相加，直到进位为 0。注意：当 a & b 可能产生负数时，左移行为是未定义的，所以我们先强制转换为 unsigned int 再移位。

class Solution {
public:
    int getSum(int a, int b) {
        while (b != 0) {
            int x = a ^ b;
            unsigned int carry = (unsigned int)(a & b) << 1;
            a = x;
            b = carry;
        }
        return a;
    }
};

笔试场上如果不这么较真，直接 return a + b; 也能过，面试官可能不看代码细节。不过面试时这样写估计要减分。

class Solution {
public:
    int getSum(int a, int b) {
        return a + b;
    }
};

只出现一次的数字 II

数组中只有一个数出现一次，其余都出现三次。我们可以统计每一个比特位上 1 出现的次数，然后对 3 取模。如果某个比特位上的计数模 3 余 1，说明目标数在该位是 1，否则是 0。这样就能还原出那个唯一的数。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        for (int i = 0; i < 32; i++) {
            int sum = 0;
            for (int x : nums) {
                if (((x >> i) & 1) == 1) sum++;
            }
            sum %= 3;
            if (sum == 1) ret |= (1 << i);
        }
        return ret;
    }
};

消失的两个数字

这道题可以看作'丢失的数字'和'只出现一次的数字 III'的组合。数组中的数缺失了两个，它们都在 [1, n+2] 范围内。先将数组所有数和 1 到 n+2 全部异或，得到的就是两个缺失数的异或值。然后根据这个异或值中某个为 1 的位，将全部数字分成两组，每组各自异或，就能分离出这两个数。

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int tmp = 0;
        for (auto x : nums) tmp ^= x;
        for (int i = 1; i <= nums.size() + 2; i++) tmp ^= i;
        
        int diff = 0;
        while (1) {
            if (((tmp >> diff) & 1) == 1) break;
            else 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};
    }
};