Background

之後可能會有一系列的文章來記錄一下在 LeetCode 上刷題所遇到的困難。

Problem

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

ex: Input: a = 1, b = 2 Output: 3
ex: Input: a = -2, b = 3 Output: 1

簡單的來說就是不能用 + or - 去做運算。

Solution

當你看到不能做正常運算時,通常都要轉成二進位做邏輯運算(AND, OR, XOR XNOR)。那我們先複習一下二進位怎麼做加法運算的。舉個例子: 121 + 37:

# 121 & 37 轉成二進位分別為
121 => 1111001 
37  => 0010011

          
                    1100001  <- carrry
  1111001            1111001 (121)          1111001
+ 0100101      -> +  0100101 (037)     xor  0100101
-----------       -----------           -------------
                    10011110 (158)          1011100 
     

我們稍微解釋一下上面的過程,一個很普通的二進位加法,但比較特別的是我們在運算加法時都會有carry值(進位),那carry發生在上下兩個值都為1的情況我們會產生進位,所以可以用 a&b 來表示carry發生的位置。那接著我們介紹另外一個邏輯運算XOR,那在加法的運算中 XOR 代表當下那個位置運算後的結果(忽略carry)。

那接著我們可以任何 a + b = a&b<<1 + a^b。

a&b<<1: a&b是發生carry的位置,往左移可以表示真正的carry
a^b: 運算後那個位置的值

那我們會發現 a&b<<1 + a^b 其實還是會有加法的存在,那接著帶入遞迴的概念 a&b<<1 種有一天會變成0,就會變成 0 + a^b 那就是 a^b 。 所以我們程式會有遞迴的概念直到 a&b<<1 變成 0。

Code

def getSum(a, b):
    if b == 0:
        return a;

    return getSum(a^b, a&b << 1)

res = getSum(1, 2)
print(res)

Reference