位运算实战：三道经典算法题解析
371. 两个整数之和
题目描述
不使用运算符 + 和 -，计算两个整数 a 和 b 的和。
题目示例
- 输入：
a = 1,b = 2 - 输出：
3
解法思路
这道题的核心在于理解计算机底层是如何进行加法运算的。我们可以将加法拆解为两个部分：
- 无进位相加：异或运算
^本质上就是无进位的加法。例如1 ^ 2(01 ^ 10) 得到11(3)，这相当于不考虑进位时的结果。 - 计算进位：按位与
&操作能得到哪些位置产生了进位，但进位需要向高位移动一位，所以结果是(a & b) << 1。
我们需要不断重复上述过程，直到没有进位产生（即进位值为 0），此时剩下的值就是最终结果。
C++ 代码实现
class Solution {
public:
int getSum(int a, int b) {
// 当进位不为 0 时继续循环
while (b) {
int x = a ^ b; // 无进位和
int y = (a & b) << 1; // 进位值
a = x;
b = y;
}
return a;
}
};
流程解析
137. 只出现一次的数字 II
题目描述
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
题目示例
- 输入：
[2, 2, 3, 2] - 输出：
3
解法思路
既然其他数字都出现了三次，那么对于任意一个二进制位，如果该位上所有数字的 1 的个数加起来能被 3 整除，说明目标数字在该位上是 0；否则，目标数字在该位上是 1。
