分析:
这里要求我们不能用加法、减法等运算符来实现加法运算。这里应该使用位运算来实现加法运算,实际上,这也是计算机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的和了。
代码:
class Solution { public: int getSum(int a, int b) { int sum = a; int icarry = b; while(icarry!=0) { int tmp = sum; sum = tmp ^ icarry; icarry = (tmp&icarry)<<1; } return sum; } };