371. Sum of Two Integers

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -. 计算两个整数a和b的和，但不允许使用运算符+和 - 。 Example:

Given a = 1 and b = 2, return 3.

---

思路：

异或的一个重要特性是不进位加法，那么只要再找到进位，将其和异或的结果加起来，就是最后的答案。 C++ using namespace std; class Solution { public: int getSum(int a, int b) { //递归算法 if(b==0) return a; int m = a^b; int c = (a&b) << 1;//计算进位 return getSum(c,m); } int getSum1(int a, int b) { //非递归 while(b)//b不为0时进入循环 { int m = a^b; b = (a&b) << 1;//计算进位 a = m; } return a; } }; int main() { Solution A; cout << A.getSum1(5,8) << endl; return 0; }

注意：

参考链接http://www.cnblogs.com/dyzhao-blog/p/5662891.html递归时间复杂度太高，不推荐应用了^（xor）运算符和移位(<<)异或 相同为0 不同为1例： 110 + 101 = 011(二进制)移位 << 1 （向左移1位）例： 1001 << 1 得到 10010