算法实战：位运算解决两数之和、唯一数字与缺失数字
在算法面试中，位运算往往能带来意想不到的空间和时间复杂度优化。今天我们来深入探讨三道经典题目，看看如何利用异或、按位与和比特位计数来解决整数求和、寻找单一元素以及查找缺失数字的问题。
35. 两个整数之和
题目描述
不使用运算符 + 和 -，计算两整数 a、b 之和。
解题思路
这道题的核心在于理解计算机底层是如何做加法的。我们可以将加法拆解为两个部分：
- 无进位加法：通过异或运算
^实现。例如1 ^ 1 = 0,1 ^ 0 = 1，这正好对应了二进制加法中不考虑进位的结果。 - 进位计算：通过按位与
&获取需要进位的位置，然后左移一位<< 1才是真正需要加到高位上的值。
只要进位不为 0，就需要重复上述过程，直到没有进位为止。
代码实现
class Solution {
public:
int getSum(int a, int b) {
// 当进位 b 不为 0 时，继续循环
while (b != 0) {
// 无进位相加的结果
int sumWithoutCarry = a ^ b;
// 计算进位位置并左移
int carry = (unsigned int)(a & b) << 1;
a = sumWithoutCarry;
b = carry;
}
return a;
}
};
注意：在 C++ 中，对有符号整数进行右移或左移可能涉及未定义行为，这里为了安全起见，计算进位时建议强制转换为无符号类型处理，或者确保逻辑正确。
36. 只出现一次的数字 II
题目描述
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
解题思路
既然其他数字都出现了三次，那么对于每一个二进制位来说，所有数字在该位上为 1 的总次数一定是 3 的倍数（如果该位属于重复数字）或者是 3 的倍数加 1（如果该位属于目标数字）。
因此，我们可以统计所有数字在每一位上 1 出现的总次数，然后对 3 取余。如果余数为 1，说明目标数字在这一位上是 1；否则是 0。通过遍历 32 个比特位，即可还原出目标数字。
代码实现
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ret = 0;
// 遍历整数的 32 个比特位
for (int i = 0; i < 32; i++) {
int sum = 0;
// 统计当前位上 1 的个数
for (int x : nums) {
sum += ((x >> i) & 1);
}
// 如果余数为 1，说明目标数字该位为 1
if (sum % 3 == 1) {
ret |= (1 << i);
}
}
return ret;
}
};
37. 消失的两个数字
题目描述
给定一个包含从 0 到 n 的所有整数，但缺少了两个数字的数组，找出这两个缺失的数字。
解题思路
这道题可以看作是'丢失的数字'和'只出现一次的数字 III'的结合体。核心思路依然是利用异或运算的特性：相同的数异或为 0。
- 首先将数组中的所有数字与 1 到 n+2 区间内的所有数字进行异或。由于除了两个缺失数字外，其他数字都出现了两次（一次在数组，一次在区间），它们会互相抵消。
- 最终得到的结果
ret就是两个缺失数字的异或值a ^ b。 - 因为
a和b不同，ret中至少有一位是 1。找到这个最右侧的 1，根据这一位将数字分为两组。 - 分别对这两组进行异或，就能得到
a和b。
代码实现
class Solution {
public:
vector<int> missingTwo(vector<int>& nums) {
int ret = 0;
int a = 0;
int b = 0;
// 第一步：异或所有数组元素和区间元素，得到 a ^ b
for (int num : nums) {
ret ^= num;
}
for (int i = 1; i <= nums.size() + 2; i++) {
ret ^= i;
}
// 第二步：找到 ret 中最右侧为 1 的位
int diffBit = 0;
while (((ret >> diffBit) & 1) == 0) {
diffBit++;
}
// 第三步：根据该位分组异或
for (int num : nums) {
if ((num >> diffBit) & 1) {
a ^= num;
} else {
b ^= num;
}
}
for (int i = 1; i <= nums.size() + 2; i++) {
if ((i >> diffBit) & 1) {
a ^= i;
} else {
b ^= i;
}
}
return {a, b};
}
};
通过以上三个例子，我们可以看到位运算在处理整数问题时的高效性。无论是避免进位的加法、统计比特位分布，还是利用异或消除重复项，掌握这些技巧都能让代码更简洁、性能更优。在实际开发中，遇到相关场景不妨多想想位运算的可能性。
