LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 异或运算可以看成不进位的加法，与运算则可以获取要进位的位置

0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0

0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1

计算 0101 + 0011
0101 ^ 0011 = 0110 => 未进位的结果
0101 & 0011 = 0001 => 为 1 的位置要进位，左移后与未进位结果相加即可

计算 0110 + 0010
0110 ^ 0010 = 0100
0110 & 0010 = 0010

计算 0100 + 0100
0100 ^ 0100 = 0000
0100 & 0100 = 0100

计算 0000 + 1000
0000 ^ 1000 = 1000
0000 & 1000 = 0000 => 无进位值，结束

结果即为 1000

• 解法如下

class Solution {
 public:
  int getSum(int a, int b) {
    int sum = a ^ b;
    int carry = static_cast<unsigned>(a & b) << 1;
    if (carry) {
      return getSum(sum, carry);
    }
    return sum;
  }
};