題目網址：https://leetcode.cn/problems/sum-of-two-integers/

題意：給兩整數 a 和 b, 在不使用 +、 - 運算的情況下, 返回兩整數之和。

Solution：

想法：將加法拆分成無進位加法、進位這兩個部分

  • XOR：為無進位的加法, 透過 a ^ b 得到無進位的加法結果, 還需要找到進位的數, 並把這兩者相加才能得到答案

  • &、shift：a & b 把 a、b 中相同位置皆為 1 的 bit 設為 1, 最後再將 a & b 左移一位即可得到進位的數
    e.g. a = 5, b = 4, 則進位數 = a & b = 0100, 但 0100 並非進位的數, 1000 才是真正進位的數

因此, 我們的步驟如下：

  • 得到 a 和 b 的進位數
  • 得到無進位加法
  • 循環此過程, 直到 carry = 0

e.g. a = 5, b = 4

  • 得到 carry b = (a & b) << 1 = 1000、無進位加法 a = (a ^ b) = 0001
  • 得到 carry b = (a & b) << 1 = 0000、無進位加法 a = (a ^ b) = 1001
  • b = 0 表示 carry = 0 要結束循環, 得到答案 a = 1001 = 9
class Solution {
public:
    int getSum(int a, int b) {
        while (b != 0) {
            const int carry = (a & b) << 1;
            a ^= b;
            b = carry;
        }
        return a;
    }
};
  • time：$O(1)$ ➔ 最多計算 32 次
  • space：$O(1)$ ➔ 只需常數空間