371
寫到 LeetCode 371. Sum of Two Integers 時，一開始想到的直觀解法是迴圈或位元操作，但是嘗試迴圈寫法無法通過 test cases ，原因是效率太低，先附上這個看起來很陽春的解法，這個寫法雖然很直觀，可是很沒有效率，所以還是應該來用一下 bit operation 的方法試試看。
class Solution {
public:
int getSum(int a, int b) {
int ans=0;
if (a<0)
{
for(int i=0; i>a; i--)
ans--;
}
else if(a>0)
{
for(int i=0; i<a; i++)
ans++;
}
else
{
ans=ans;
}
if (b<0)
{
for(int i=0; i>b; i--)
ans--;
}
else if(b>0)
{
for(int i=0; i<b; i++)
ans++;
}
else
{
ans=ans;
}
return ans;
}
};
於是接下來就嘗試用 bit operation 的方法來做，先看一個簡單的 case，假設現在 a=2, b=3，各自用二進位表示，a=00000010,b=00000011，我們希望得到的答案是 5 (二進位表示就是00000101)，如果寫成直式加法，我們的運算過程會是
- 加總最右邊的 LSB，得到答案的第一位是 1
- 加總右邊數來第二個 bit，得到一個要進位的 1，填到答案的第三位
- 因為已經進位，所以將 0 填入答案的第二位
在程式的實作上，應該先考慮的是要進位的那個值(在程式中用 carry 表示)，所以我們可以先用 (a&b)<<1 得到 carry = 00000100，然後用 (a^b) 得到 sum = 00000001，概念上有點像是先計算有沒有要進位(得到第三位的值)、再計算(去掉要進位的值之後)最右邊兩位的加總值。
接下來是比較困難的部分 - 結束條件，因為上面的例子只是讓我們了解演算法大概要怎麼做，但是少考慮到整個演算法要怎麼執行。其實這一塊的想法也很簡單。一開始我們是有 a 跟 b 這兩個數值要相加，經過上面的運算，我們可以得到 carry 跟 sum，那我們只要再把 sum 和 carry 相加一次就好，對應到程式實作的話，就是用 sum 和 carry 取代 a 跟 b 。
但是怎麼知道，這樣的程序要進行到什麼時候才能停呢?
答案就是 - 不需要進位就可以直接得到加總答案的時候。比如說，如果是要加總 1 跟 2，我們可以直接用 (00000001 ^ 00000010) 得到 (00000011)，也就是 3 。在這個例子中, carry 會是 (00000001 & 00000010) = (00000000)，如果我們判斷 carry 是 0，就可以回傳結果了。
根據以上觀念，就可以實作出以下的程式碼啦!
class Solution {
public:
int getSum(int a, int b) {
while (b != 0) {
int sum = a ^ b;
int carry = (a & b) << 1;
b = carry;
a = sum;
}
return a;
}
};
如果想要更了解這個加法的話，可以去看看 Half Adder 的介紹。
**Update: 把loop改成recursive 把結果存在sum裡面，如果carry為零就完成運算
public int getSum(int a, int b) {
if(b == 0){//没有进为的时候完成运算
return a;
}
int sum,carry;
sum = a^b;//完成第一步加发的运算
carry = (a&b)<<1;//完成第二步进位并且左移运算
return getSum(sum,carry);//
}