leetcode解题: Sum of Two Integers (371)

发表于 | 分类于

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.

解法1：Iteration

XOR是一个不带进位的加法运算，进位的信息可以通过AND（与运算）再左移获得。可以有Recursion和Iteration两种写法
C++

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
    public int getSum(int a, int b) {
        while (b != 0) {
            int c = a ^ b;
            int carry = (a & b) << 1;
            a = c;
            b = carry;
        }
        return a;
    }
}

解法2：Recursion

C++

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    public int getSum(int a, int b) {
      if (b == 0) {
        return a; // stop condition
      }
      int c = a ^ b;
      int carry = (a & b) << 1;
      return getSum(c, carry);
    }
}