매일 LeetCode 풀기 | Sum of Two Integers

 

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

 

정말 접근조차 쉽지 않았던 문제였다. 

 

class Solution {
    func getSum(_ a: Int, _ b: Int) -> Int {
        var a = a 
        var b = b 

        while b != 0 {
            let carry = a & b 
            a = a ^ b 
            b = carry << 1 
        }
        
        return a
    }
}

 

접근 방식 
: 덧셈의 본질은 두 수를 더하고, 올림을 처리하는 과정 

1. a는 현재까지의 덧셈 결과를 저장함 (올림 제외) 
2. b는 다음에 처리해야 할 올림을 저장함 
3. b가 0이 된다는 건, 더 이상 처리할 올림이 없다는 뜻 = 모든 자리의 덧셈과 올림 처리가 완료되었음 
예시) 3(011) + 2(010) 더할 때 -> 1회차: a = 001, b = 100 (아직 올림 있음), 2회차: a = 101, b = 000 (올림 없음) 

 

연산자 
1. &(AND 연산자) : 두 비트가 모두 1일 때만 1을 반환 
2. ^(XOR 연산자) : 두 비트가 서로 다를 때 1을 반환 
3. << (왼쪽 시프트 연산자) : 비트를 왼쪽으로 지정된 수만큼 이동시킴