(Leetcode) 371 - Sum of Two Integers

1월 31일날 문제를 풀고 2월 9일인 이제서야 정리를 하게 되었다.

New Year Gift - Curated List of Top 75 LeetCode Questions to Save Your Time

위 링크에 있는 추천 문제들을 시간이 있을때마다 풀어보려고 한다.

Sum of Two Integers

이 문제는 python에서 기본적으로 제공해주는 + 나 - 를 사용하지 않고 연산을 처리해주면 되는 문제이다.

binary 연산을 통해서 해결할 수 있다.

최종 코드는 다음과 같다.

class Solution:
    def getSum(self, a: int, b: int) -> int:
        MAX = 0x7FFFFFFF
        mask = 0xFFFFFFFF

        while b != 0:
            a, b = (a ^ b) & mask, ((a & b) << 1) & mask

        if a > MAX:
            a = ~(a ^ mask)

        return a

2의 보수

참고로 입력값들은 음수도 허용된다. 따라서 이 문제를 풀기 위해서는

• bit 연산
• 2의 보수
• 1의 보수

와 같은 개념을 알아야 한다.

예시로 생각해보는 계산 과정

만약 a 가 217이고 b가 -318 이였다면 어떻게 될까? (이렇게 수를 정한 이유는 크게 없다. 무작위로 정했으며 2의 n승인 숫자는 피하려고 했다.)

차근차근 계산해보자.

• ^ 는 xor 연산이다. 대응되는 비트가 서로 다르면 1을 반환한다.
• & 는 and 연산이다. 대응되는 비트가 모두 1이면 1을 반환한다.
• « 는 지정한 수 만큼 비트들을 왼쪽으로 이동시킨다. (shift left)
• ~ 는 NOT 연산이다. 1의 보수를 반환 한다.
• 예시로 정한 입력값에서 a는 양수고 b는 음수다. 따라서 bit 연산할 때 음수는 2의 보수 처리를 해줘야 한다.
• a는 둘이 더해졌을 때의 값(carry 무시)을 b는 carry 값(더하면서 발생된 올림 수)을 보관하게 된다.

이후 만약 a가 MAX 보다 크다면 음수인 것을 의미한다. 음수라면 다시 2의 보수를 취해줘야 한다.

a가 음수이기 때문에 a ^ mask 는 모든 수를 반전시킨다 (여기까지가 1의 보수)

~ 연산자가 알아보다보니 조금 묘했다. 공식문서에서는 다음과 같이 설명한다.

Returns the complement of x - the number you get by switching each 1 for a 0 and each 0 for a 1. This is the same as -x - 1.

~ 연산자는 해당 값을 부호 비트를 바꾸고 1을 뺀것과 같은 효과를 준다. 이를 통해서 2의 보수가 될 수 있다.

python의 int 범위, python 의 음수 양수 처리 방식

python은 int의 범위가 unbound이다. python도 음수인지 양수인지 체크를 별도의 부호 비트를 사용한다. 따라서 C같은 언어처럼 int의 범위가 지정되어 있고 첫번째 비트를 사용하는 방식은 아니다.

이로인해 식 중간중간에 불필요 해보이는 ^ mask 가 들어가 있는 것이다. (32bit으로 제한해서 처리하기 위해)

참고

bit 연산자에 대한 설명은 FAQ: What do the operators <<, >>, &, |, ~, and ^ do?를 참고하면 좋을 것 같다.