72. Sum of Two Integers

아현·2021년 5월 24일
0

Algorithm

목록 보기
73/400

리트코드


  • 두 정수 ab의 합을 구하라.

    • +또는 - 연산자는 사용할 수 없다.



1. 전가산기 구현 (28ms)


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
            





  • 이번에는 좀 더 제대로 전가산기를 구현해본다. 물론 전가산기를 온전히 구현하는 데는 많은 노력이 필요하다.

    • 지나치게 어렵게 풀이하는 것 같지만, 여기서는 논리 회로에 대한 이해도 높일 겸 한 번 제대로 구현을 시도해본다.

<전가산기 회로도>

  • 전가산기 회로도는 AND 게이트 2개, XOR 게이트 2개, OR 게이트 1개로 이루어져 있다.


<각각의 게이트 위치 중간값 표현>


  • 그림의 중간값 변수 Q1, Q2, Q3에 회로도의 연산을 통해 직접 계산해보자.

    • 이를 파이썬 코드로 구현하면 다음과 같다.

       Q1 = A & B        
        Q2 = A ^ B        
        Q3 = Q2 & carry   
        sum = carry ^ Q2  
        carry = Q1 | Q3  
      
    • 각각의 비트는 이렇게 전가산기를 통해 합 sum을 구하는 로직으로 처리할 수 있게 되었다.

  • 다음으로 이를 위한 전처리를 진행한다.

    • bin()이라는 함수는 십진수 100b1010으로 변환해준다.

    • 이 때 앞에 0b식별자가 항상 붙는다.

      • 우리에게는 필요 없는 값이므로, 슬라이싱 bin(a)[2:0]로 이 부분을 떼낸다.
    • MASK는 비트 마스크로, 음수 처리를 위해 2의 보수로 만들어주는 역할을 한다.

      • 여기서는 입력값을 32비트 정수로 가정했으므로 MASK0xFFFFFFFF로 했고, 이 값을 AND 연산하면 이제 결과는 2의 보수 값을 취하게 된다.

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

    • 양수인 경우 마스킹을 해도 동일하지만 음수인 -1은 2의 보수에서 가장 큰 값이기 때문에, 이처럼 마스킹을 할 경우 32비트 전체가 1로 꽉 채워지는 모습을 확인할 수 있다.

      • z.fill(32)로 32비트 자릿수를 맞춰준다.

      • 앞자리가 비어 있으면 계산을 어렵게하기 때문이다.


  • 전처리를 다 끝내었고 이제 처리한 값을 뒷부분부터, 즉 낮은 자릿수부터 하나씩 전가산기를 통과하면서 결과를 채워나가면 된다.

    • 여기서는 32비트를 가정했으므로 32번 반복한다.

  • 마지막 반복이 끝난 후 아직 carry값이 남아 있다면 자릿수가 하나 더 올라간 것이므로, 1을 더 추가한다.

    • 이렇게 되면 최대 33비트가 되겠지만, 마지막 마스킹 작업을 통해 이 값은 날아가게 될 것 이다.
  • result는 낮은 자릿수부터 채웠으므로, 뒤집은 다음 십진수 정수로 바꿔준다.

    • 다음으로 마스킹을 해서, 만약 자릿수를 초과했다면 그 값은 제거될 수 있게 한다.

  • 마지막으로 음수를 처리하는데, 2의 보수에서 음수는 32번째 비트의 값, 즉 최상위 비트(MSB)가 1인 경우다.

    • 양의 정수 최댓값은 0x7FFFFFFF이므로, 만약 32번째 비트가 1이라면 이보다 큰 값이 되고, 이 경우 마스킹 값과 XOR한 다음 NOT 처리를 해서 다시 음수로 만들어준다.



2. 좀 더 간소한 구현 (24ms)


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)
       
        #합, 자릿수 처리
        while b != 0:
            a,b = (a ^ b) & MASK, ((a & b) << 1) & MASK
        
        #음수 처리
        if a > INT_MAX:
            a = ~(a ^ MASK)
        return a
        


  • 여기서는 핵심만 살려서 간단하게 동작 가능하게 한다.

  • MASK는 2의 보수로 만들기 위한 것으로, 이전 풀이와 동일한 값이다.

  • ab의 역할을 구분해 a에는 carry 값을 고려하지 않는 ab의 합(sum)이 담기게 하고, b에는 자릿수를 올려가며 carry 값이 담기게 했다.

  • 다음으로 음수에 대한 처리를 해준다.

    • XOR -> NOT
profile
Studying Computer Science

0개의 댓글