LeetCode.371.Sum of Two Integers

题目描述

• 371 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.

解题过程

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

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

总结：

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

不用递归的话，代码为：

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代码

• leetcode-java / problems / _371_SumOfTwoIntegers /
  https://github.com/masikkk/leetcode-java/tree/master/problems/_371_SumOfTwoIntegers