LeetCode#371. Sum of Two Integers

发表于 | 分类于 ， ，

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.

分析

按照题目的要求，不能使用+和-，那只能使用位运算了。这样的话，很容易就能想到使用&来进行计算，通过计算两个数每一位的与，以及下一位与的结果，就可以知道当前位的值。但是由于不能用+，所以即使计算出了结果的每一位，也没办法计算出最后的值。

既然&可以计算出进位，那么是否有其他的位运算可以计算出当前位的值？那就是^了。通过异或计算出的值是不含进位的，因此在异或之后需要和进位结果再异或一次，以得出新的值。但是这次计算又可能产生新的进位，因此需要循环直到不再含有进位。代码如下：

1
2
3
4
5
int getSum(a, b)
  while (b != 0)
  	carry = a & b    // 计算出需要进位的位
  	a = a ^ b
  	b = carry << 1   // 左移一位即可得出进位结果