LeetCode.371.Sum of Two Integers 不用加减号计算整数加法

题目描述

371 Sum of Two Integers
https://leetcode-cn.com/problems/sum-of-two-integers/
https://leetcode.com/problems/sum-of-two-integers/description/

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.

---

相似题目

LeetCode.371.Sum of Two Integers 不用加减号计算整数加法
LeetCode.067.Add Binary 二进制求和

LeetCode.剑指offer.064.计算1到n的和

LeetCode.069.Sqrt(x) x的平方根
LeetCode.050.Pow(x,n) 实现Pow(x,n)

---

解题过程

不用+-符号计算整数加法。
想着应该是用位运算来做，但还是不会。一点儿思路都没有，最后上网搜了一下，可涨知识了。

思路如下：
从二进制的角度考虑，在不考虑进位的情况下a+b=a^b，由于只有1+1时才有进位，所以可以通过先做按位与(&)运算再左移(<<)1位来得到进位，最后将无进位的和与进位相加就是结果。

异或 ^ 被称为不进位的加号
左移 << 是一种进位或者乘法符号
公式：a + b = ( a ^ b ) + ( ( a & b ) << 1 )

对于本题
1、a + ba 的问题拆分为 (a 和 b 的无进位结果) + (a 和 b 的进位结果)
2、无进位加法使用异或运算计算得出
3、进位结果使用与运算和移位运算计算得出
4、循环此过程，直到进位为 0

不用递归的话，代码为：

class Solution {
    public int getSum(int a, int b) {
        int sum = a ^ b;//不考虑进位的和
        int carry = (a & b)<<1;//进位
        while(carry!=0){//直到进位为0，结束
            int newsum = sum ^ carry;
            carry = (sum & carry)<<1;
            sum = newsum;
        }
        return sum;
    }
}

用递归的话就更简单了，只需要一行：

class Solution {
    public int getSum(int a, int b) {
        return b==0 ? a : getSum(a^b,(a&b)<<1);
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_371_SumOfTwoIntegers.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_371_SumOfTwoIntegers.java

---