LeetCode 371 Sum of Two Integers
===============================
Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.
Example:Given a = 1 and b = 2, return 3.
這里考察的是是否理解計(jì)算機(jī)如何實(shí)現(xiàn)加減法運(yùn)算蝌借。
加法運(yùn)算由多位串聯(lián)的全加器實(shí)現(xiàn)码泞，而每個(gè)全加器實(shí)際上又由半加器組成。如下圖給出了一個(gè)4bit的加法器。
假設(shè)有兩個(gè)bit：a0和b0孵睬，半加器的邏輯：
$s0 = a0 xor b0$
$s0 = a0 & bo$
假設(shè)有兩個(gè)4bit的整數(shù)相加：a3a2a1a0 + b3b2b1b0，則
$sum = a xor b = (a3 xor b3) (a2 xor b2) (a1 xor b1) (a0 xor b0)$
每一位分別異或運(yùn)算源请，求取不考慮進(jìn)位的各位之和
$carry = a & b = (a3 & b3) (a2 & b2) (a1 & b1) (a0 & b0)$
每一位分別與運(yùn)算馏臭，求取當(dāng)前這種不考慮進(jìn)位的加法，各位兩個(gè)bit相加后產(chǎn)生的進(jìn)位
下面就到了最trick的部分名扛，由于當(dāng)前的sum未考慮進(jìn)位谅年，因?yàn)榧由蟘arry才是真正的結(jié)果。
那carry應(yīng)該怎么作用到sum上呢肮韧？實(shí)際上carry是每一bit的進(jìn)位（此處是4bit）融蹂，第i位的進(jìn)位應(yīng)該作用到i+1位上，用公式可以表達(dá)為
$sum = sum + 2 * carry = s3s2s1s0 + c3c2c1c0 << 1$
要注意的是弄企，sum和carry的相加還會(huì)產(chǎn)生新的sum和carry超燃，由于高位的carry先傳遞給高位，但低位的carry還沒有傳遞到拘领，因此sum與carry的相加需要循環(huán)多次意乓，知道carry為0時(shí)，加法才真正結(jié)束约素。這里的carry左移届良，與半加器中carryout的傳遞相對(duì)應(yīng)笆凌，第一次左移代表，a0b0的carryout傳遞完畢士葫，不再考慮a0b0的部分乞而，第二次左移代表a1b1的carryout傳遞完畢，不再考慮a1b1为障，以此類推直到a3b3晦闰。
這里的carry整體左移，再直接作用到sum上有一些難以理解鳍怨，特別是sum直接異或carry求取不考慮進(jìn)位的和，這里一開始可能感覺這個(gè)加法不正確跪妥，但實(shí)際上鞋喇，第i次的sum xor carry僅僅是確定了倒數(shù)第i位的和，剩余的carry信息仍在傳遞且加法沒有結(jié)束眉撵，這里一定能夠要能夠理解這種carry傳遞的思維侦香。
public class Solution {
public int getSum(int a, int b) {
while (b != 0) {
int carry = a & b;
a = a ^ b;
b = carry << 1;
}
return a;
}
}
