位运算核心技巧与实战解析

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

2.2 比特位计数

题目：返回从 0 到 n 每个数字二进制中 1 的个数。

思路：对每个数单独调用上述方法统计，或者利用动态规划优化，但基础解法已足够直观。

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

2.3 汉明距离

题目：计算两个整数二进制表示中不同位的个数。

思路：先异或 x ^ y，不同位即为 1，再统计结果中 1 的个数。

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

2.4 只出现一次的数字

题目：数组中除一个数字外，其他都出现两次，找出那个唯一的数。

思路：利用 a ^ a = 0 和 a ^ 0 = a，全部元素异或即可抵消成对的数字。

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

2.5 只出现一次的数字 III

题目：数组中有两个数字只出现一次，其余出现两次，找出这两个数。

思路：所有数异或得到 t = a ^ b。找到 t 中任意为 1 的位（如最右侧 1），根据该位将数组分为两组，分别异或即可得到两个数。

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        unsigned int t = 0;
        for (auto x : nums) t ^= x;
        
        int t1 = 0, t2 = 0;
        // 获取最右侧的 1
        int c = t & (-t);
        
        for (auto x : nums) {
            if ((x & c) == 0) t1 ^= x;
            else t2 ^= x;
        }
        return {t1, t2};
    }
};

3. 进阶练习题

3.1 判断字符是否唯一

题目：判断字符串中是否包含重复字符。

思路：小写字母共 26 个，可用一个整型变量作为位图。遍历字符串，检查对应位是否已置 1。注意鸽巢原理，长度大于 26 直接返回 false。

class Solution {
public:
    bool isUnique(string astr) {
        if (astr.size() > 26) return false;
        int t = 0;
        for (auto x : astr) {
            int cur = int(x - 'a');
            if ((t >> cur) & 1) return false;
            t |= (1 << cur);
        }
        return true;
    }
};

3.2 丢失的数字

题目：找出 [0, n] 范围内缺失的一个数字。

思路：

1. 位运算法：将 0 到 n 全部异或，再与数组元素异或，成对出现的会抵消，剩下缺失的数。
2. 高斯求和：计算 0 到 n 的和，减去数组元素总和。

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

3.3 两整数之和

题目：不使用 + 和 - 计算两数之和。

思路：

• 无进位和：a ^ b
• 进位：(a & b) << 1
• 递归或循环直到进位为 0。

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

3.4 只出现一次的数字 II

题目：除一个数字外，其他都出现三次，找出那个唯一的数。

思路：统计每一位上 1 出现的总次数，对 3 取模，余数为 1 则该位属于目标数字。

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

3.5 消失的两个数字

题目：找出 [1, n] 中缺失的两个数字。

思路：类似'只出现一次的数字 III'，先对所有数字（包括缺失的）与数组元素异或，得到两个缺失数的异或值，再分组求解。

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        unsigned int s = 0;
        int n = nums.size() + 2;
        for (int i = 1; i <= n; i++) s ^= i;
        for (auto x : nums) s ^= x;
        
        int t = s & (-s);
        int ret1 = 0, ret2 = 0;
        
        for (auto x : nums) {
            if (x & t) ret1 ^= x;
            else ret2 ^= x;
        }
        for (int i = 1; i <= n; i++) {
            if (i & t) ret1 ^= i;
            else ret2 ^= i;
        }
        return {ret1, ret2};
    }
};

通过上述练习，希望能帮助大家建立位运算的思维模型。在实际编码中，灵活运用这些技巧往往能让代码更简洁高效。