박종훈 기술블로그

(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의 보수

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

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

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

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

차근차근 계산해보자.

example2

이후 만약 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?](https://wiki.python.org/moin/BitwiseOperators)를 참고하면 좋을 것 같다.