【Leetcode每日一题】位运算 - 两整数之和（难度⭐）（37）

1. 题目解析

题目链接：371. 两整数之和

这个问题的理解其实相当简单，只需看一下示例，基本就能明白其含义了。

2.算法原理

算法的核心思路其实可以类比为我们小时候学习的加法运算。只不过这次，我们不是在纸上用铅笔算，而是在计算机里用二进制数字来进行。这个算法巧妙地利用了异或（^）和按位与（&）这两种位运算来实现二进制数的加法。

异或运算：模拟不进位的加法

异或运算在二进制的世界里，就像是两个小朋友在做加法，但他们只关心当前位的和，不考虑进位。比如，1 + 1 在十进制里是2，但在异或运算里，1 ^ 1 等于 0，就像两个小朋友说：“我们这一位加起来是0，不用进位哦！”同样地，0 ^ 0、0 ^ 1、1 ^ 0 都分别等于 0、1、1，就像是他们正确地计算出了每一位的和。

按位与运算：找出需要进位的位

但是，小朋友们也知道，有时候加法是需要进位的。这时候，按位与运算就像是另一个小朋友，专门负责找出哪些位需要进位。比如，1 & 1 在二进制里是1，这意味着这一位两个小朋友加起来满2了，需要向高位进1。而0 & 0、0 & 1、1 & 0 都等于0，表示这些位不需要进位。

循环进行，直到没有进位

有了这两个小朋友（异或和按位与），我们就可以开始计算加法了。首先，我们用异或运算得到当前不考虑进位的和。然后，我们用按位与运算找出哪些位需要进位。如果发现有进位，我们就把这些进位加到下一轮的运算中。这样一轮一轮地进行，直到所有的进位都处理完，也就是按位与的结果变成0，我们就得到了最终的和。

这个算法虽然看起来有些复杂，但其实非常高效。因为它直接在二进制位上进行操作，避免了十进制加法中可能需要的多次进位和借位。在计算机内部，这种位运算的速度是非常快的，所以这种算法在处理大量数据时特别有用。

3.代码编写

class Solution 
{
public:
    int getSum(int a, int b) 
    {
        while(b != 0)
        {
            size_t x = a ^ b;
            size_t y = (size_t)(a & b) << 1;
            a = x;
            b = y;
        }
        return a;
    }
};