位运算实战：判断字符唯一性与查找缺失数字

汉明距离

461. 汉明距离 - 力扣（LeetCode）

C++ 算法代码：

class Solution {
public:
    int hammingDistance(int x, int y) {
        int count = 0;
        int ret = x ^ y; // 不同位为 1
        while(ret) {
            ret &= (ret - 1);
            count++;
        }
        return count;
    }
};

只出现一次的数字

136. 只出现一次的数字 - 力扣（LeetCode）

C++ 算法代码：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int val = 0;
        for(auto e : nums) {
            // 相同数字异或为 0，最终剩下唯一的数
            val ^= e;
        }
        return val;
    }
};

只出现一次的数字 III

260. 只出现一次的数字 III - 力扣（LeetCode）

C++ 算法代码：

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        if(nums.size() == 2) {
            return nums;
        }
        sort(nums.begin(), nums.end());
        vector<int> res;
        int ans = 0;
        for(int i = 0; i < nums.size(); i++) {
            ans ^= nums[i];
        }
        for(int i = 0; i < nums.size(); i += 2) {
            if(nums[i] != nums[i + 1]) {
                res.push_back(nums[i]);
                ans ^= nums[i];
                break;
            }
        }
        res.push_back(ans);
        return res;
    }
};

判定字符是否唯一

题目描述

给定一个字符串，请判断其中是否包含重复字符。要求不使用额外的数据结构（如哈希表）。

面试题 01.01. 判定字符是否唯一 - 力扣（LeetCode）

解题思路：位图映射

既然不能用哈希表，我们可以利用整数本身的二进制位来充当'标记'。假设输入只包含小写字母，那么最多只有 26 个不同的字符。一个 int 类型有 32 位，足以容纳这 26 个状态。

我们可以把整数的每一位看作一个开关：

• 如果第 k 位是 0，表示对应字符还没出现过。
• 如果第 k 位是 1，表示该字符已经出现过。

这样，一个整数就替代了哈希表的功能，空间复杂度降到了 O(1)。

C++ 算法代码

class Solution {
public:
    bool isUnique(string astr) {
        // 如果字符串长度超过 26，根据鸽巢原理必有重复
        if(astr.size() > 26) {
            return false;
        }
        
        int m = 0; // 作为比特位哈希表
        
        for(int i = 0; i < astr.size(); i++) {
            // 计算当前字符对应的偏移量 'a' -> 0, 'b' -> 1...
            int shift = astr[i] - 'a';
            
            // 检查第 shift 位是否已经是 1
            // (m >> shift) & 1 取出该位的值
            if((m >> shift) & 1) {
                return false; // 已存在，说明重复
            }
            
            // 将该位置为 1，标记字符已出现
            m |= (1 << shift);
        }
        
        return true;
    }
};

流程解析

查找缺失的数字

题目描述

给定一个包含 [0, n] 中 n 个不同整数的数组，找出其中缺失的那个数。

268. 丢失的数字 - 力扣（LeetCode）

解题思路：异或消去

这道题有多种解法，比如高斯求和公式，但位运算中的异或（XOR）特性更为精妙。

异或运算有一个重要性质：A ^ A = 0，且 A ^ 0 = A。这意味着相同的数异或会抵消为 0。

如果我们把数组中的所有元素，以及完整的序列 0 到 n 全部放在一起异或，那么成对出现的数字都会变成 0，最后剩下的结果就是那个只出现一次的缺失数字。

C++ 算法代码

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int ret = 0;
        // 遍历数组，将索引 i+1 与 nums[i] 进行异或
        // 初始 ret 相当于 0，循环结束后相当于 0^1^2...^n ^ nums[0]^nums[1]...
        for(int i = 0; i < nums.size(); i++) {
            ret ^= nums[i] ^= (i + 1);
        }
        return ret;
    }
};

流程解析

小结

这两道题展示了位运算在算法设计中的两种典型应用：

1. 位图思想：用整数的二进制位压缩存储状态，节省空间。
2. 异或特性：利用自反性消除重复项，直接定位异常值。

掌握这些技巧，能在处理特定约束（如无额外空间、大数据量）时提供高效的解决方案。