Leetcode 371. Sum of Two Integers

Daehwi Kim·2021년 6월 30일

leetcode

LeetCode

목록 보기

21/23

371. Sum of Two Integers

Medium

Given two integers a and b, return the sum of the two integers without using the operators + and -.

Example 1:

Input: a = 1, b = 2
Output: 3

Example 2:

Input: a = 2, b = 3
Output: 5

Constraints:

-1000 <= a, b <= 1000

풀이

1. 전가산기 구현을 통한 풀이

class Solution:
    def getSum(self, a: int, b: int) -> int:
    	# 비트마스크 : 음수처리를 위한 비트 설정
        MASK = 0xFFFFFFFF
        # 정수 최대값(32비트의 MSB는 0값이어야 양수 비트의 최대값이다.)
        INT_MAX = 0x7FFFFFFF

	# 32비트의 2진수 값 전처리
        a_bin = bin(a & MASK)[2:].zfill(32)
        b_bin = bin(b & MASK)[2:].zfill(32)

	# 비트를 담을 변수 설정
        result = []
        
        # carry 설정
        carry = 0
        
        # 합계 설정
        sum = 0

	# 32비트 횟수 만큼 반복문을 돌면서 전가산기 동작 구현
        for i in range(32):
            # LSB 부터 비트를 본다
            A = int(a_bin[31-i])
            B = int(b_bin[31-i])
			
            # 각 게이트별 계산
            Q1 = A & B
            Q2 = A ^ B
            Q3 = Q2 & carry
            sum = Q2 ^ carry
            carry = Q1 | Q3

   	    # 각 비트의 합을 결과값리스트에 추가
            result.append(str(sum))

	# 마지막 carry(자리올림수)가 남아있으면 결과값에 추가
        if carry == 1:
            result.append('1')
		
        # 초과된 자리수 비트마스크로 없애버리기(32비트로 가정했으니, 32비트가 넘어가면 안됨)
        result = int(''.join(result[::-1]), 2) & MASK

	# 음수값이라면 2의보수를 이용하여 음수처리
        if INT_MAX < result:
            result = ~(MASK ^ result)
        
        return result

간소화한 풀이

class Solution:
    def getSum(self, a: int, b: int) -> int:
    	# 비트 마스크
        MASK = 0xFFFFFFFF
        # 최대 정수비트
        INT_MAX = 0x7FFFFFFF
        
        # 자리 올림수가 0이 아닐때까지 반복
        # a = 각비트의 합
        # b = 자리가 올려진 carry 값
        while b != 0:
            a, b = (a ^ b) & MASK, ((a & b) << 1) & MASK
        
        # 음수 처리
        if a > INT_MAX:
            a = ~(a^MASK)
            
        return a