【LeetCode】两整数之和_0110+0100有进位吗

不使用运算符 + 和 - ，计算两整数 ​​​​​​​a 、b ​​​​​​​之和。

示例 1:

输入: a = 1, b = 2
输出: 3

示例 2:

输入: a = -2, b = 3
输出: 1

import java.lang.reflect.Array;
import java.util.*;
 
public class Main {
 
    public static void main(String[] args)
    {
 
        Scanner sc=new Scanner(System.in);
        int a=sc.nextInt();
        int b=sc.nextInt();
 
        System.out.println(Solution.getSum(a,b));
 
    }
 
}
 
 
class Solution {
    public static int getSum(int a, int b) {
 
        if ((a&b)==0)            //没有进位时 ，返回ab或运算的结果（即a+b）
            return a|b;
        return getSum(a^b,(a&b)<<1);//还有进位时 ，a=a^b,b=(a&b)<<1,递归运算
 
    }
}

思路：两数相加等价于两数的二进制形式不进位和（即异或运算）与进的位（与运算）左移一位再相加（即或运算）。

如：

3+7=10

3=0011

7=0111

3+7=(3^7)+(3&7)<<1即 0011^0111和(0011&0111)<<1相加——> 0100和0110相加

这时候 0100和0110相加还有进位，所以递归为：

0100^0110和(0100&0110)<<1相加——>0010和1000相加

这时候0010和1000相加没有进位了，所以返回的是0010|1000=1010即回到原式3+7的结果等于10。