[LeetCode] 371. Sum of Two Integers - Java

https://leetcode.com/problems/sum-of-two-integers/description/

Sum of Two Integers - LeetCode

---

문제

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

---

풀이

풀이 과정

"+" 와 "-"를 사용하지 않고 주어진 두 수 a, b의 합을 구하는 문제이다.
이 문제에서는 비트연산을 사용한다.

비트 연산자에는 다음과 같은 종류가 있다.

• AND( & ) : 각 자리의 비트가 모두 1일 때 1을 반환, 하나라도 0일 경우 0
• OR( | ) : 각 자리의 비트 중 하나라도 1일 때 1을 반환, 모두 0일 경우 0
• XOR( ^ ) : 각 자리의 비트가 서로 다르면 1을 반환, 같으면 0
• NOT( ~ ) : 각 자리의 비트가 1이면 0, 0이면 1로 반전
• LEFT SHIFT( << ) : 지정된 수 만큼 비트를 왼쪽으로 이동, 비워진 비트는 0으로 채워짐
• RIGHT SHIFT( >> ) : 지정된 수만큼 비트를 오른쪽으로 이동, 첫 번째 비트에 따라 빈 공간이 채워짐

이 중 덧셈을 하는데 필요한 부호는 XOR, AND, LEFT SHIFT 3가지 이다.

우선 두 수의 XOR 연산을 수행하면 각 자리수가 하나는 0 하나는 1일때만 1을 반환하고, 둘 다 0이거나 둘다 1일 때는 0을 반환하므로 올림수를 제외한 덧셈의 결과를 구할 수 있다.

다음으로 두 비트의 각 자리수가 모두 1일 때만 1을 반환하는 AND 연산을 수행한 후 왼쪽으로 한 자리씩 옮기게 되면 올림 수룰 구해낼 수 있다.

이렇게 구한 덧셈 결과와 올림 수를 각각 a, b로 위의 연산을 반복적으로 수행하다 a나 b가 0이 될 때, 즉 더 이상 연산이 필요 없어질 때 나머지 값을 return 하면 두 수 의 합을 구할 수 있다.

ex)

a = 2, b = 3인 경우
이진수로 나타내었을 때 각각 0010, 0011
XOR 연산을 수행하면 가장 오른쪽 비트가 다르므로 1이되고 나머지는 0이된다.
AND 연산을 수행했을 때 오른쪽에서 두 번째 비트만 모두 1이므로 0010이 되고 왼쪽으로 shift하여 0100이 된다.
이 두 결과를 가지고 동일한 연산을 반복수행

XOR 연산을 수행했을 때 가장 오른쪽 비트와 오른쪽에서 세 번재 비트가 다르므로 0101이되고
AND 연산을 수행했을 때 둘 다 1이 되는 비트가 없으므로 0000이 된다.
AND, SHIFT 연산을 한 결과값이 0이되어 더 이상 연산이 필요 없으므로 나머지인 0101, 10진수로 나타내었을 때 5를 구할 수 있다.

---

최종 코드

class Solution {
    public int getSum(int a, int b) {
        /*
         * 두 수 중 한쪽의 값이 0이 된다면 
         * 0이 아닌 쪽의 값을 return
         */
        if(a == 0) return b;
        if(b == 0) return a;

        int sum = a ^ b;         // 올림수 제외하고 더한 결과
        int carry =(a & b) << 1; // 올림수

        // getSum 함수를 재귀 호출
        return getSum(sum, carry);
    }
}

---