[😭 LeetCode Python] 371. Sum of Two Integers

📌

문제 및 문제설명

---

371. Sum of Two Integers

+, -을 이용하지 않고 합을 구하는 문제

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

Sum of Two Integers - LeetCode

 

 

📌

풀이

---

# 전가산기를 이용한 풀이

def getSum(self, a: int, b: int) -> int:
        MASK = 0xFFFFFFFF #보수용 mask
        INT_MAX = 0x7FFFFFFF # 양의 정수 중 가장 큰 수
        
        # 이진수로 바꾸고 0으로 채워줌
        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])
            
            Q1 = A & B
            Q2 = A^B
            Q3 = Q2&carry
            SUM = carry ^ Q2
            carry = Q1|Q3
            
            result.append(str(SUM))
            
        if carry == 1:
            result.append('1')
        
        # 초과 자릿수 처리 
        result = int(''.join(result[::-1]),2) & MASK 
        
        # 음수처리
        if result > INT_MAX: #최댓값보다 크다는 건 음수라는 뜻
            result = ~(result^MASK)
        
        return result

# 간략화한 풀이

def getSum(self, a: int, b: int) -> int:

        MASK = 0xFFFFFFFF #보수용 mask
        INT_MAX = 0x7FFFFFFF # 양의 정수 중 가장 큰 수
        
        while b!=0:
            a, b = (a^b) & MASK, ((a&b) << 1) & MASK

        if a > INT_MAX:
            a = ~(a^MASK)
            
        return a