位运算实战：两整数之和与只出现一次的数字

前言

算法题的核心往往在于对底层逻辑的深刻理解。今天聚焦两道经典的位运算题目，通过实际代码剖析异或、按位与以及比特位计数的应用技巧。

36. 两个整数之和

题目链接： 371. 两整数之和 - 力扣（LeetCode）

题目描述：

题目示例：

解题思路

在计算机底层，加法本质上是二进制位的运算。既然不能使用 + 运算符，我们可以拆解加法的两个核心部分：

无进位加法：使用异或 ^ 运算。例如 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
            unsigned int carry = (unsigned int)(a & b) << 1;
            a = x;
            b = carry;
        }
        return a;
    }
};