[Leetcode 아주 상세한 문제풀이] 371. Sum of Two Integers - 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 371번 문제 Sum of Two Integers 다.

우선 문제를 살펴보자.

 

리트코드 371번 문제 Sum of Two Integers 링크

Sum of Two Integers - LeetCode

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가 주어진다. 이때 a와 b의 합을 구해야 하는데 더하기나 빼기 연산을 사용하지 말고 두 정수의 합을 구하라는 문제다. 문제가 너무 간단해 더 이상 문제를 설명할 것이 없다. 곧바로 문제를 풀어보도록 하자.

 

 

문제 접근법

더하기 (+)나 빼기 (-) 연산을 이용하지 않고 두 정수의 함을 구하기 위해 우리는 bitwise operation을 이용할 것이다. 

 

 

우선 XOR와 AND operation에 대해 알 필요가 있다.

1) XOR operation

XOR operation은 두 개의 bit이 다를 경우 1 같은 경우 0을 리턴한다.

예를 들어 1+1=0 (올림이 생김)이 되고 1+0=1이 된다.

우리는 인풋으로 입력받은 두 개의 정수를 bit으로 바꿔 XOR 연산을 통해 더하기를 할 것이다.

2) AND operation

AND operation은 두 개의 bit이 1일 경우만 1을 리턴한다.

예를 들어 1+1=1이 된다.

우리는 AND operation을 올림을 계산하는데 사용할 것이다.

정리하면 우리는 인풋으로 입력받은 정수 a, b를 bit으로 바꿔 연산을 할 것이다.

그 둘을 더하기 위해 XOR operation을 이용할 것인데 이때 숫자를 올려야 하는 경우가 발생한다.

그 올림을 위한 연산을 위해 AND operation을 이용할 것이다.

Bitwise operation에 대해 익숙하지 않다면 조금 어려울 수도 있지만 코드를 통해 하나씩 살펴보자.

 

 

문제 풀이

두 개의 정수 a, b를 입력받기 위한 함수를 정의해 준다. (line 1)

우리는 32 bit 정수 최대값을 설정해 줄 것인데 만약 a, b의 합이 이보다 클 경우 음수임을 의미한다. (line3)

추가로 32 bit 정수의 mask를 설정해줄 것이다. (line 5)

파이썬에서는 정수를 표현하기 위해 다양한 길이의 bit을 갖는데 길이 통일을 위해 mask를 이용한다.

우리는 연산을 통해 b를 a에 더해줄 것이다.

따라서 b를 모두 a에 더해주고 나면 남는 bit이 없기 때문에 b에 bit이 남아있는한 연산을 계속한다. (line 7)

우선 정수 a,b를 더해주는데 앞서 설명한 XOR operation을 통해 더해준다.

그리고 그 크기를 고정하기 위해 mask와 AND 연산을 해준다.

XOR operation의 경우 a, b는 더할 수 있지만 올림이 발생할 경우 처리할 수 없다.

따라서 우리는 AND operation을 통해 올림을 계산해야 한다.

올림이 발생할 경우 left shift (<<) operation을 통해 계산해준다.

그리고 이 역시 길이 통일을 위해 mask와 AND 연산을 해준다. (line 9)

결과적으로 이 과정을 마치고 나면 b가 a에 더해졌다.

a를 리턴하기 전 우선 a가 MAX값 보다 같거나 작은지 확인한다.

만약 a가 MAX 값보다 같거나 작다면 이는 음수가 아닌 32 bit 정수이므로 그대로 리턴하면 된다. (line 13)

그렇지 않다면 a는 음수이기 때문에 그에 따른 추가로 NOT operation 연산을 주어야 한다.

 

 

문제 풀이 코드

def get_sum(a, b):
    # 32 bits integer max
    MAX = 0x7FFFFFFF
    # Mask to get 32 bits
    mask = 0xFFFFFFFF
    
    while b != 0:
        # ^ gets different bits and & gets double 1s, << moves carry
        a, b = (a ^ b) & mask, ((a & b) << 1) & mask
    
    # if a is negative, get a's 32 bits complement positive first
    # then get 32-bit positive's Python complement negative
    return a if a <= MAX else ~(a ^ mask)
 
# Example usage:
print(get_sum(1, 2))  # Output: 3
print(get_sum(2, 3))  # Output: 5
 

 

 

 

관련 문제

리트코드 190번 Reverse bits 문제 풀이 링크

리트코드 191번 Number of 1 bits 문제 풀이 링크

리트코드 268번 Missing number 문제 풀이 링크

리트코드 338번 Counting bits 문제 풀이 링크

 

371. Sum of Two Integers