LeetCode 371. Sum of Two Integers

파이썬 알고리즘 인터뷰 72번(리트코드 371번) Sum of Two Integers
https://leetcode.com/problems/sum-of-two-integers/

다른 풀이1

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

        a_bin = bin(a & MASK)[2:].zfill(32)
        b_bin = bin(b & MASK)[2:].zfill(32)

        result = []
        carry = 0
        sum = 0

        for i in range(32):
            A = int(a_bin[31-i])
            B = int(b_bin[31-i])

            sum = A ^ B ^ carry
            carry = ((A | B) & carry) | (A & B)
            result.append(str(sum))
            
        ''' 사실 없어도 됨
        if carry == 1:
            result.append('1') 
        '''
        result = int(''.join(result[::-1]), 2) & MASK
        
        if result > INT_MAX: # result // (2**31) == 1 도 가능
            result = ~(result ^ MASK)
        return result

다른 풀이2

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

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

        return a & mask if b > 0 else a

배운 점

• 비트 연산자
• 2의 보수
• 음수 표현 방법
• 파이썬은 고정된 비트 수 없이 무한히 확장되는 임의 정밀도 정수를 지원하므로 비트 연산 시 MASK를 이용해야한다.
• 위 내용들 모두 가벼운 내용이 아니라 풀이를 이해하는데 오래 걸렸다. 아직 남에게 설명할 정도로 완벽히 이해하지 못했다. 추후 더 공부하고 나서 위 내용들을 정리하는 글을 아래에 추가하겠다.