位运算算法实战：从字符唯一性到缺失数字查找

算法实现

class Solution {
public:
    bool isUnique(string astr) {
        // 利用鸽巢原理做优化
        if (astr.size() > 26) return false;
        
        int bitMap = 0;
        for (char ch : astr) {
            int i = ch - 'a';
            // 检查第 i 位是否已经是 1
            if ((bitMap >> i) & 1) return false;
            // 将第 i 位设为 1
            bitMap |= (1 << i);
        }
        return true;
    }
};

关键点

实际编码时，注意位移操作的优先级。(bitMap >> i) & 1 用于读取特定位，bitMap |= (1 << i) 用于设置特定位。推导过程中建议自己在纸上画出二进制变化过程，这有助于理解位图映射的本质。

034 丢失的数字

题目描述： 给定一个包含 [0, n] 中 n 个数的数组，找出其中没有出现的那个数。

解法思路：异或消去

数组长度为 n，原本应该包含 0 到 n 共 n+1 个数。现在少了一个。

如果我们把数组中的所有元素，以及 0 到 n 的所有数字全部进行异或运算，根据异或的特性（相同为 0），成对出现的数字都会抵消为 0，最终剩下的就是那个缺失的数字。

算法实现

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int ret = 0;
        // 异或数组中的元素
        for (int x : nums) ret ^= x;
        // 异或 0 到 n 的所有数字
        for (int i = 0; i <= nums.size(); i++) ret ^= i;
        return ret;
    }
};

关键点

这种方法空间复杂度为 O(1)，时间复杂度为 O(n)。不需要额外的哈希表或排序，非常高效。核心在于理解'成对抵消'的逻辑。

035 两整数之和

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

解法思路：模拟加法器

计算机底层加法是通过逻辑门电路实现的，可以分为两步：

1. 无进位相加：使用异或 ^ 运算。1 ^ 1 = 0, 0 ^ 0 = 0, 1 ^ 0 = 1。
2. 计算进位：使用按位与 & 运算并左移一位。1 & 1 = 1，进位发生在高位。

循环执行这两个步骤，直到进位为 0，此时 a 即为最终结果。

算法实现

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

关键点

注意进位计算时使用了 unsigned int 强制转换。因为如果 a & b 的结果是负数（最高位为 1），直接左移可能导致未定义行为。转换为无符号数后左移是安全的。虽然面试中可以直接写 return a + b;，但掌握底层原理对理解计算机组成至关重要。

036 只出现一次的数字 II

题目描述： 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

解法思路：比特位计数

既然其他数字都出现了三次，那么对于任意一个比特位，如果我们将所有数字在该位上的值加起来，总和应该是 3 的倍数加上目标数字在该位的值（0 或 1）。

因此，遍历 32 个比特位，统计每一位上 1 出现的次数。如果次数模 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++;
            }
            if (sum % 3 == 1) {
                ret |= (1 << i);
            }
        }
        return ret;
    }
};

关键点

此方法适用于'出现 K 次找 1 次'的通用场景。虽然代码嵌套了两层循环，但外层固定为 32，整体时间复杂度仍视为 O(n)。处理负数时需注意补码表示，上述逻辑对补码同样有效。

037 消失的两个数字

题目描述： 给定一个包含 0 到 n 中 n 个数的数组，其中有两个数字消失了，找出这两个数字。

解法思路：组合拳

这道题其实是前面两道题的结合版：

1. 类似于'丢失的数字'，先将数组中的数和 1 到 n+2 区间内的所有数异或在一起。这样得到的结果是两个缺失数字的异或值（记为 tmp）。
2. 类似于'只出现一次的数字 III'，我们需要找到区分这两个缺失数字的某一位。tmp 中为 1 的位，说明这两个缺失数字在这一位上不同。
3. 根据这一位将原数组和完整序列分为两组，分别异或，即可得到两个缺失数字。

算法实现

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int tmp = 0;
        // 1. 异或所有数字
        for (int x : nums) tmp ^= x;
        for (int i = 1; i <= nums.size() + 2; i++) tmp ^= i;
        
        // 2. 找到 tmp 中为 1 的最低位（区分位）
        int diff = 0;
        while (!((tmp >> diff) & 1)) diff++;
        
        // 3. 分组异或
        int a = 0, b = 0;
        for (int x : nums) {
            if ((x >> diff) & 1) b ^= x;
            else a ^= x;
        }
        for (int i = 1; i <= nums.size() + 2; i++) {
            if ((i >> diff) & 1) b ^= i;
            else a ^= i;
        }
        return {a, b};
    }
};

关键点

关键在于找到区分位 diff。只要找到任意一个不同的比特位，就能将两个目标数分到不同的组里，从而通过异或消除其他干扰项。这种分治思想在位运算题目中非常经典。

结语

位运算不仅是面试中的高频考点，更是理解计算机底层数据处理的基石。掌握这些技巧，不仅能写出更高效的代码，还能在面对复杂问题时找到意想不到的突破口。建议在练习时多尝试自己推导二进制变化过程，加深理解。