LeetCode Problem-Sum of Two Integers

這道題挺經典的，之前自學python的時候看過這樣一個例子，這裡記錄一下思路。

題目描述：

給定兩個整數，實作a + b但不用 + 或 - 操作符

思路

一開始可能會覺得奇怪，不給使用四則運算還玩什麼？但這是計算機問題，可以回顧一下加法和減法的具體操作（減法是加法的逆運算，視為同理）

對于 a + b = c 而言，不妨以十進制舉例，對于 15 + 17 = 32而言，可以先視作

1.按位相加

2.根據有無進位繼續做加和

從底層實作的角度來看，這裡跟 加法器 的原理是一緻的，隻是底層是二進制而不是十進制罷了。

半加器原理：

S = ~A & B + A & ~B = A^B (按位加和）

C = A & B （進位判斷）

因為存在進位的情況，是以在這道題的實作中，需要在相加之後做一個 << 1 操作，總代碼實作如下

int getSum(int a, int b) {
    if(b == 0)return a;
    int carry = (a & b) << 1;
    int sum = a ^ b;
    return getSum(sum,carry);
    
}
複制代碼