[LeetCode] 371. Sum of Two Integers

Problem

Given two integers a and b, return the sum of the two integers without using the operators + and -.

Example 1:

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

Example 2:

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

Constraints:

• -1000 <= a, b <= 1000

---

Solution

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

Explanation

• 먼저 정수 a 혹은 b 둘 중 하나가 0이면 상대 정수를 반환하면 되므로 그에 따른 if조건문을 작성한다.

  if (a == 0 || b == 0) return a == 0 ? b : a;
  

• 덧셈과 뺄셈 연산자를 사용지 않고 두 정수의 덧셈을 수행하기 위해 비트 연산을 사용한다.
• 두 수를 더할 때 고려해야할 사항이 바로 올림의 발생이다. 비트 연산에서 올림이 발생하는지 알기 위해서 변수 carry를 선언하고 두 수를 이용해 AND(&)연산을 수행 한 값을 할당한다.

  int carry = a & b;
  

• 두 수를 이용해 XOR(^)연산을 수행하면 올림을 제외한 두 수의 덧셈 결과를 알아낼 수 있다.
• 두 수의 XOR연산 결과를 새로운 변수에 할당할 수도 있지만 이미 존재하는 변수 a에 할당하고 변수 b를 올림으로 활용하여 문제를 해결한다.

  int carry = a & b;
  a = a ^ b;
  b = carry << 1;
  

• 반복을 위해 while반복문을 선언하고 while반복문을 나왔을 때의 계산 결과인 변수 a를 반환한다.

  while (b != 0) {
    int carry = a & b;
    a = a ^ b;
    b = carry << 1;
  } return a;