[leetcode] 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.

分析：
这里要求我们不能用加法、减法等运算符来实现加法运算。这里应该使用位运算来实现加法运算，实际上，这也是计算机CPU内部实现加法运算的方案。
x XOR y真值表:
x y output
0 0 0
0 1 1
1 0 1
1 1 0
x AND y真值表:
x y output
0 0 0
0 1 0
1 0 0
1 1 1
我们可以基于以上的真值表用&和^{运算来实现加法，每一位的}运算得到每一位上的不加进位的和，用&运算得到每一位的进位。
根据上面的分析，我们可以加x，y的每一位逐一进行XOR和AND运算，然后得到最后的结果。但如果要得到每一位，还要用到AND运算。
比方说00001010，
要取倒数第二位的值（1），其值为：00001010&00000010
要取倒数第三位的值（0），其值为：00001010&00000100
要取倒数第四位的值（1），其值为：00001010&00001000
而且这样还没用真正得到每一位上的值，还要进行操作。
首先，我们通过对x和y进行&位运算，得出每一位上的进位。然后对x和y进行^位运算，得出没有加进位的和。最后将所得的和当做新的x，所得的进位往左移一位(第零位的进位输入为0)当做新的y，继续做上面的步骤，直到进位为0，此时x中保存的就是我们要求的x和y的和了。

1 int bitAdd(int a,int b)
2 {
3 if(b==0)
4 return a;
5 int sum = a^b;
6 int carry =(a&b)<<1;
7 return bitAdd(sum,carry);
8 }

int getSum(int a, int b) {
while(b)
{
int carry = a & b;
a = a ^ b;
b = carry << 1;
}
return a;
}