[Algorithm] LeetCode 371. Sum of Two Integers (javascript)— 位元運算

題目：Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -. 不使用+和 -，計算出兩數的總和。

解答：

function getSum (a, b) {  
  if(b===0) return a;  
  var sum=a^b;  
  var carry=(a & b) << 1;  
  return getSum(sum, carry);
};

解法是利用位元運算子( Bitwise operator )與位移運算子( Shift operator )對數值的位元進行運算。

原理：

在做加法運算的時候，每位相加之後可能會有進位Carry產生，然後在下一位計算時需要加上進位一起運算。例如：在計算 694+1210時，不考慮進位的話結果是 1804，只考慮進位的話結果是 0100（因爲在十位數的地方有一個進位，往前進一位得到0100)。2者相加的結果是1904。

同理也可以運用在進行2進位的運算上，假設a=3, b=5，他們的二進位分別是a=0011, b=0101，不考慮進位時，2者相加爲0110，只考慮進位的話結果是0001，往前進1位變成0010，2數相加是1000，也就是十進位中的8。

二進位中不考慮進位的算法就是XOR(異或)的運算規則，只考慮進位的算法就是AND(與)的運算規則，往前進1位就是shift的運算。

XOR(^, Exclusive or): 當2個bit不相同時，輸出1，當2個bit相同時，輸出0

AND(&): 當2個bit都是1時，輸出1，其他情況輸出0

Shift operator

<<(Zero fill left shift): 將位元左移，右邊補上 0。

按步驟分解：

function getSum (a, b) {  
  if(b===0) return a;  
  var sum=a^b;  
  var carry=(a & b) << 1;  
  return getSum(sum, carry);
};
getSum(3, 5)
1: a=0011, b=0101, sum=0110, carry=0001<<1=0010
2: a=0110, b=0010, sum=0100, carry=0010<<1=0100
3: a=0100, b=0100, sum=0000, carry=0100<<1=1000
4: a=0000, b=1000, sum=1000, carry=0000
5: a=1000, b=0000, b===0, return a

參考：

• https://stackoverflow.com/a/55193241
• https://www.jianshu.com/p/9235a7980934