[LeetCode] 371. Sum of Two Integers

문제

leetcode.com/problems/sum-of-two-integers/

Sum of Two Integers - LeetCode

 

잠깐만

비트 연산인데, 아이디어가 없으면 코드 바로 보세요~

 

코드

class Solution {
    func getSum(_ a: Int, _ b: Int) -> Int {
        var tempB = (a & b) << 1
        var tempA = a ^ b

        if tempB == 0 {
            return tempA
        } else if tempA == 0 {
            return tempB
        } else {
            return getSum(tempA, tempB)
        }
    }
}

 

설명

학부생 1학년때 배웠었나요? 너무 오래돼서 그런지 기억은 안나네요.

 

2와 3을 2진수 덧셈 연산으로 계산해볼게요

10과 11을 더하면 101이 된다는 것을 사람은 알고 있죠.

그럼 계산 수식을 어떻게 알고리즘으로 풀어야 할까요?

검정색 숫자 "01"은 "10"과 "11"의 XOR 연산 값(같으면 0, 다르면 1)이며

빨간색 숫자 "10"은 "10"과 "11"의 AND 연산 값(모두 1이면 1, 아니면 0)입니다.

따라서 다음과 같이 XOR와 AND 연산이 필요합니다.

물론 빨간색 숫자인 AND 연산 값은 자릿수가 변경되니, 시프트도 필요합니다.

결과적으론 다음과 같은 로직이 완성됩니다.

짜잔~

 

여러가지 예제까지 손으로 그려봤어요 참고하세요

회고

너무 오랜만의 비트 연산이라, 당혹스러웠어요.

여러분도 그랬나요?

혹여나 그랬다면, 이 문제로, 좌절하지 마세요.

너무 오랜만에 본 로직이니깐 충분히 그럴 수 있습니다.