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

36. 两个整数之和

题目链接：

371. 两整数之和 - LeetCode

题目描述：

给定两个整数 a 和 b，不使用运算符 + 和 - ，计算两整数之和。

题目示例：

输入：a = 1, b = 2 输出：3

解法（位运算）：

算法思路：

• 异或 ^ 运算本质是【无进位加法】
• 按位与 & 操作能够得到【进位】
• 然后一直循环，直到【进位】变成 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;
    }
};

---

37. 只出现一次的数字 II

题目链接：

137. 只出现一次的数字 II - LeetCode

题目描述：

给你一个整数数组 nums ，除某个元素仅出现一次外，其余每个元素都恰出现三次。找出并返回那个只出现了一次的元素。

题目示例：

输入：nums = [2,2,3,2] 输出：3

解法（比特位计数）：

算法思路：

设要找的数为 ret。 由于整个数组中，需要找的元素只出现了【一次】，其余的数都出现【三次】，因此我们可以用根据所有数的【某一个比特位】的总和 %3 的结果，快速定位到 ret 上的【一个比特位上】的值是 0 还是 1。 这样我们通过 ret 的每一个比特位上的值，就可以将 ret 还原出来。

C++ 算法代码：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        for (int i = 0; i < 32; i++) // 依次去修改 ret 中的每一位
        {
            int sum = 0;
            for (auto x : nums) // 计算 nums 数组中所有数第 i 位的和
                if ((x >> i) & 1) sum++;
            sum %= 3;
            if (sum == 1) ret |= (1 << i);
        }
        return ret;
    }
};