LeetCode-Sum of Two Integers

發表於 更新於 分類於 閱讀次數： Disqus：

計算兩個整數的和，但是不允許使用加、減運算子

Test Case

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

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

如果可以用的話這一題就直接 a + b 就好了，是吧，想也知道沒那麼膚淺；這一題解題思路就是利用邏輯運算子來處理。

我們都知道數字可以轉成二進制，例如：23 跟 7 這兩個數字相加，會變成像是下面這樣子

1
2
3
// 23 :  10111
//  7 :  00111
// 30 :  10222

可是二進制並沒有 2 這種東西，碰到 2 就是進位，所以實際上應該是

1
// 30 : 11110

OK，到這邊再看一下邏輯閘的概念，

AND 1 0
1 1 0
0 0 0

AND邏輯閘很好理解，只要兩者都為真值，輸出則為真。

OR 1 0
1 1 1
0 1 0

OR邏輯閘也是一樣，只要兩者有一個是真值，輸出就為真

XOR 1 0
1 0 1
0 1 0

互斥或閘就比較難理解了，如果沒有概念的話可以參考一下電子電路的互斥或閘邏輯圖

原文出處：Understanding Gates – XOR Gate

從上圖可以很清楚的看到，互斥或閘的邏輯，紅線的部分表示真值，在兩者相同的情況下，輸出皆為0。

回過頭來看一下二進制相加的這個問題，我們將計算拆成兩個部分，第一個部分是數字相加有進位的部分，第二個部分則是沒有進位的部分，所以我們期望得到的數值，應該是

1
2
3
4
5
6
7
8
// 23  :  10111
//  7  :  00111
// 30  :  10222
// 30  :  11110
// ============
// x   :  10000
// y   :  01110

X 這個變數我們可以透過 XOR Gate 得到，但是 y 這個進位的怎麼辦？其實也不難，就利用 AND Gate接著再將結果左移一個位元就好了。

1
2
3
// ============
// x   :  10000  --> XOR gate
// y'  :  01110  --> AND gate , then left shift

在Csharp裡面可以直接透過邏輯運算子來進行數字的二進制邏輯運算，所以我們不需要自行將數字轉二進制，在一個一個去做邏輯運算

可是如果，我的XOR與AND計算得出的數字，兩者之和又剛好需要再進位怎麼辦呢？
那就把這兩個數字，再重新計算一次數字相加就可以了，到最後，如果進位的數字等於0，表示XOR的運算結果就是答案了

所以，可以得到如下程式碼

1
2
3
4
5
6
7
public class Solution {
    public int GetSum(int a, int b) {
        var x = a ^ b;  // XOR 運算結果
        var y = ((a & b) << 1); // AND 運算結果再左移一位元，表示進位的數字
        return y==0 ? x : GetSum(x,y); // 如果不需要進位，則XOR就是答案；否則再重新計算兩者之和
    }
}

這次的練習其實一開始只知道概念是利用二進制計算，如果用手寫的我大概瞬間就知道怎麼解，但是要利用csharp來進行邏輯運算，一開始真的卡了很久，因為對邏輯運算子很不熟，還以為需要先轉二進制，再一個一個位元下去比對，Convert來Convert去的，搞得頭昏腦脹，經過大神解說後，才發現根本不用這樣子搞，直接透過csharp提供的運算子來做就好了。

這一題大概就是考考二進制的觀念，以及邏輯閘，當然遞迴處理也可以換成while迴圈，終止條件一樣是判斷進位即可。
總的來說，簡單，又很有趣。