LeetCode 题解-371. Sum of Two Integers

对Leetcode 371. Sum of Two Integers 题目的求解。

Problem Description#

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

Example 1#

1
Input: a = 1, b = 2
2
Output: 3

Example 2#

1
Input: a = -2, b = 3
2
Output: 1

Analysis#

在不使用内置加法运算的情况下求两个数的和，我们需要依赖位运算．在位运算中我们需要关注两种运算

异或．两个数异或的结果恰恰是不进位加法的结果．
与．两个数与运算后的结果恰恰是进位的结果．

所以对于a+b,我们求得异或和与的结果之后，再将两个结果相加，长此以往，直到其中一个为零：没有进位了，或者加法结果恰好为2^n．

Solution 1: bfs with recursive call#

1
class Solution{
2
    public static int getSum(int a, int b) {
3
        while (a != 0 && b != 0){
4
            int tmp = a ^ b;
5
            b = (a & b) << 1;
6
            a = tmp;
7
            //System.out.printf("%d %d\n", a, b);
8
        }
9
        if (a == 0) return b;
10
        else return a;
11
    }
12
｝