[Leetcode] 리트코드 - 두 정수의 합(sum-of-two-integers) 파이썬(python) 풀이

문제

두 정수 a와 b의 합을 구하라. +또는 -연산자는 사용할 수 없다.

입력
a = 1, b = 2

출력
3

입력
a = -2, b = 3

출력
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])

            # 전가산기 구현
            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

좀 더 간소한 구현

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

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

풀이

전가산기 구현

아래의 그림은 A와 B의 전 가산기 회로이다.

Sum은 A와 B의 XOR을 한 뒤에 다시 Carry in과 XOR을 한 값이다. 왜냐하면 XOR은 두 개가 다를시 1을 반환하기 때문에 결국 더했을 때 그 자리에 올 수와 같다. 즉 A, B를 XOR하고 그 값을 Carry in과 XOR을 하면 sum(그자리에 올 0 or 1)값이 된다.

Carry out은 A와 B가 둘다 1이어서 밑의 AND 연산으로 1이되고, 그 밑의 or 연산으로 1이되어 올림수가 발생하는 경우와 또 다른 하나는 A와 B의 XOR 연산 즉 둘 중 하나만 1이어서 XOR로 1이 되고, Carry in이 1이되어서 그 밑의 AND연산으로 1, 그 밑의 or 연산으로 최종 1이 반환되어 올림수가 발생하는 경우 이렇게 2가지이다.

이제 이 그림의 중간값 변수 Q1, Q2, Q3에 회로도의 연산을 통해 직접 계산해보자. 이를 파이썬 코드로 구현해보면 다음과 같다.

Q1 = A & B
Q2 = A ^ B
Q3 = Q2 & carry
sum = carry ^ Q2
carry = Q1 | Q3

각각의 비트는 이렇게 전가산기를 통해 합 sum을 구하는 로직으로 처리할 수 있게 됐다. 다음으로 이를 위한 전처리를 진행해보자.

MASK = 0xFFFFFFFF
a_bin = bin(a & MASK)[2:].zfill(32)

a 정수를 a_bin이라는 이진수로 변경하는 데 몇 가지 전처리 작업을 진행했다. 하나씩 살펴보면, 먼저 bin() 함수는 십진수 10을 이진수 0b1010으로 변환해준다.

>>> bin(10) 
'0b1010'

이때 파이썬에서는 이진수로변환하면, 앞에 0b 식별자가 항상 붙는다. 우리에게는 필요 없는 값이므로, 슬라이싱 bin(a)[2:]로 이 부분을 떼낸다. 그다음으로 a & MASK의 MASK는 비트 마스크로, 음수 처리를 위해 2의 보수로 만들어주는 역할을 한다. 여기서는 입력값을 32비트 정수로 가정했으므로 MASK는 0xFFFFFFFF로 했고, 이 값을 AND 연산하면 이젠 결과는 다음과 같이 2의 보수 값을 취하게 된다.

>>> bin(1 & MASK)
'0b1'
>>> bin(-1 & MASK)
'0b11111111111111111111111111111111'

양수인 경우 마스킹을 해도 동일하지만 음수인 -1은 2의 보수에서 가장 큰 값이기 때문에, 이처럼 마스킹을 할 경우 32비트 전체가 1로 꽉 채워지는 모습을 확인할 수 있다. 다음으로 zfill(32)로 32비트 자릿수를 맞춰준다. 앞자리가 비어 있으면 계산을 하기 어렵기 때문에, 모두 0으로 해서 32비트 자릿수를 다음과 같이 모두 채워준다.

>>> '1'.zfill(32)
'00000000000000000000000000000001'

여기까지가 전처리고, 이렇게 처리한 값을 뒷부분부터, 즉 낮은 자릿수부터 하나씩 전가산기를 통과하면서 결과를 채워나간다. 여기서는 32비트로 가정했으므로, 다음과 같이 32번을 반복한다.

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')

마지막 반복이 끝난 후 아직 carry 값이 남아 있다면 자릿수가 하나 더 올라간 것이므로, 1을 더 추가한다. 이렇게 되면 최대 33비트가 되겠지만, 다음과 같이 마지막 마스킹 작업을 통해 이 값은 날아가게 된다.

result = int(''.join(result[::-1]), 2) & MASK

result는 낮은 자릿수부터 채웠으므로, 뒤집은 다음 십진수 정수로 바꿔준다. 그리고 나서 다음과 같이 마스킹을 해서, 만약 자릿수를 초과했다면 그 값을 제거될 수 있게 한다.

마지막으로 음수를 처리할 차례다. 2의 보수에서 음수는 32번째 비트의 값, 즉 최상위 비트(MSB)가 1인 경우다. 양의 정수 최댓값은 0x7FFFFFFF이므로, 만약 32번째 비트가 1이라면 이보다 큰 값이 되고, 이 경우 마스킹 값과 XOR을 한 다음 NOT 처리를 해서 다시 음수로 만들어준다. 마스킹 값과 XOR을 하게되면 1과 0이 반전이 되고, 2의 보수 체계에서 반전되면 1작은 양수가 된다. (-2이면 1) 그리고 나서 NOT(~)처리를 해서 음수를 만들어 준다. NOT x는 -x -1이다.

INT_MAX = 0x7FFFFFFF
...
if result > INT_MAX:
    result = ~(result ^ MASK)

좀 더 간소한 구현

a, b = (a ^ b) & MASK, ((a & b) << 1) & MASK

여기서 MASK는 2의 보수로 만들기 위한 것으로, 이전 풀이와 동일한 값이다. 여기서는 a와 b의 역할을 구분해 a에는 carry 값을 고려하지 않는 a와 b의 합(sum)이 담기게 하고, b에는 자릿수를 올려가며 carry 값이 담기게 했다. 다음 음수에 대한 처리를 해준다.

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

MASK를 빼고 단순 계산만 보자면 밑의 그림처럼 점점 b의 carry가 사라저 가면서 while문을 빠져나온다.

출처
파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호) [책만]