算法实战：位运算解法详解
35. 两个整数之和
题目描述
不使用运算符 + 和 -，计算两整数 a、b 之和。
解题思路
位运算的核心在于模拟加法器的逻辑。异或 ^ 运算本质上是无进位加法，而按位与 & 操作能得到需要进位的位置。由于进位需要向左移动一位才能加到正确位置，因此我们需要循环处理，直到进位变为 0。
C++ 实现
class Solution {
public:
int getSum(int a, int b) {
// 当进位不为 0 时继续循环
while (b != 0) {
int x = a ^ b; // 无进位相加
int y = (a & b) << 1; // 计算进位并左移
a = x;
b = y;
}
return a;
}
};
流程解析
36. 只出现一次的数字 II
题目描述
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
解题思路
统计所有数字在每一个二进制位上的总和。因为其他数字都出现了三次，所以除目标数字外，每一位的累加和都能被 3 整除。对每一位的累加和取模 3，即可还原出目标数字的二进制表示。
C++ 实现
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ret = 0;
// 遍历 32 位整数的每一位
for (int i = 0; i < 32; i++) {
int sum = 0;
// 统计当前位上所有数字的和
for (int x : nums) {
sum += ((x >> i) & 1);
}
// 余数即为该位的值
ret |= ((sum % 3) << i);
}
return ret;
}
};
流程解析
38. 消失的两个数字
题目描述
给定包含 0..n 中 n 个数的数组 nums，其中有两个数字消失了，找出这两个消失的数字。
解题思路
这道题可以看作是'丢失的数字'与'只出现一次的数字 III'的结合。首先将数组中的所有数与区间 [1, n+2] 的所有数进行异或，问题转化为寻找两个只出现一次的数。利用异或结果中某一位为 1 的特性，将原数组和区间数分为两组分别异或，即可分离出这两个数。
C++ 实现
class Solution {
public:
vector<int> missingTwo(vector<int>& nums) {
int ret = 0;
int a = 0, b = 0;
// 第一步：全部异或，得到两个消失数的异或值
for (int num : nums) ret ^= num;
for (int i = 1; i <= nums.size() + 2; i++) ret ^= i;
// 第二步：找到 ret 最右侧为 1 的比特位
int x = 0;
while (((ret >> x) & 1) == 0) x++;
// 第三步：根据该位是否为 1 分组异或
for (int num : nums) {
if (((num >> x) & 1) == 0) a ^= num;
else b ^= num;
}
for (int i = 1; i <= nums.size() + 2; i++) {
if (((i >> x) & 1) == 0) a ^= i;
else b ^= i;
}
return {a, b};
}
};
流程解析
总结
这三道题目展示了位运算在不同场景下的威力。第一题通过模拟硬件加法器逻辑解决求和问题；第二题利用比特位计数特性提取唯一值；第三题则通过分组策略将复杂问题拆解。代码实现均注重时间复杂度优化，适合面试及工程实践参考。
