前言
位运算在处理底层数据时往往能带来意想不到的效率提升。本文将通过两道经典算法题，深入探讨如何利用位运算特性解决常规算术无法直接处理的问题。
371. 两整数之和
题目描述：
不使用运算符 + 和 -，计算两整数 a、b 之和。
算法思路： 这道题的核心在于理解计算机底层的加法逻辑。加法可以拆解为两个部分：无进位相加和进位。
- 异或（^）：相当于无进位加法。例如
1 ^ 1 = 0，1 ^ 0 = 1。 - 按位与（&）并左移（<<）：相当于计算进位。只有当两个位都为 1 时才产生进位，且进位需要加到下一位。
我们需要不断重复这两个步骤，直到进位变为 0，此时剩下的结果即为最终的和。
C++ 实现：
class Solution {
public:
int getSum(int a, int b) {
while (b) {
int x = a ^ b; // 先算出无进位相加的结果
unsigned int carry = (unsigned int)(a & b) << 1; // 再算出进位
a = x;
b = carry;
}
return a;
}
};
注意： 在计算进位时，需要将 a & b 的结果强制转换为 unsigned int，防止有符号整数左移导致未定义行为。
137. 只出现一次的数字 II
题目描述： 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
算法思路： 既然其他数字都出现了三次，那么对于二进制表示的每一位来说，所有数字在该位上的 1 出现的总次数应该是 3 的倍数。如果目标数字在该位上是 1，那么该位的总和模 3 余 1；如果是 0，则模 3 余 0。
因此，我们可以遍历整数的 32 个比特位，统计数组中所有数字在该位上 1 的个数，然后对 3 取模。如果余数为 1，说明目标数字在这一位上是 1，将其累加到结果中。
C++ 实现：
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++; // 统计第 i 位为 1 的次数
}
sum %= 3;
if (sum == 1) ret |= (1 << i); // 还原目标数字的该位
}
return ret;
}
};
这种解法的时间复杂度是 O(32 * N)，空间复杂度是 O(1)，非常高效。它不依赖哈希表，也不依赖排序，纯粹利用位运算的特性完成了任务。
