[파이썬 알고리즘 인터뷰][비트연산] 두 정수의 합

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

+ / - 없이 정수의 덧셈 구현

 

책에서 구현된 코드

class Solution:
    def getSum(self, a: int, b: int) -> int:
        MASK = 0xFFFFFFFF
        INT_MAX = 0x7FFFFFFF
        # 합, 자릿수 처리
        while b != 0:
            a, b = (a ^ b) & MASK, ((a & b) << 1) & MASK

        # 음수 처리
        if a > INT_MAX:
            a = ~(a ^ MASK)
        return a

 

기억해야할 기법

• 비트연산을 구현할 때 자리수가 미리 지정되어야함

 

내가 구현한 코드

class Solution:
    def getSum(self, a: int, b: int) -> int:
        cnt = 1023
        mask = 0b1
        carry = 0
        res = 0
        while cnt:
            res |= carry ^ (a & mask) ^ (b & mask)
            if carry != 0:
                carry = (carry & ((a & mask) | (b & mask))) << 1
            else:
                carry = ((a & mask) & (b & mask)) << 1

            mask = mask << 1
            cnt = cnt >> 1

        if (res & (mask >> 1)):
            return (~res ^ 1023)
        return res

• 자리수 제한 없는 덧셈을 만들어보고 싶었는데, 오버플로우 기준이 없으면 음수 표현이 안된다