LeetCode 371 - Sum of Two Integers

+나 - 같은 산술 연산자를 사용하지 않고 두 정수 a와 b의 합을 구하는 Medium 문제다. 비트 단위 XOR 연산으로 자리 올림 없는 덧셈을 수행하고, AND 및 시프트 연산으로 자리 올림(Carry)을 계산하는 하드웨어 가산기(Adder) 원리를 적용했다.

---

문제 링크 & 설명

• 문제 링크: 371. Sum of Two Integers
• 요약: 연산자 + 및 -를 직접 사용하지 않고 두 정수 a와 b의 합을 반환한다.

컴퓨터 하드웨어에서 덧셈기는 두 비트의 덧셈 결과를 XOR (^)로, 자리 올림수를 AND (&)로 계산한다. 파이썬은 정수의 비트 수가 무제한으로 확장되므로, 32비트 마스킹(0xFFFFFFFF)을 통해 32비트 정수 오버플로 및 음수 2의 보수 표현을 명시적으로 제어해야 한다.

---

접근 방법

mask = 0xFFFFFFFF와 32비트 양수 최댓값 max_int = 0x7FFFFFFF를 설정한다.

mask = 0xFFFFFFFF
max_int = 0x7FFFFFFF

while b != 0:
    carry = (a & b) << 1
    a = (a ^ b) & mask
    b = carry & mask

return a if a <= max_int else ~(a ^ mask)

1. 자리 올림 계산: (a & b) << 1로 두 비트가 모두 1인 위치의 자리 올림수를 구하고 한 칸 왼쪽으로 시프트한다.
2. 자리 올림 없는 합 계산: a ^ b로 각 자리의 합을 구하고 32비트 마스크를 적용한다.
3. 반복 갱신: 더 이상 자리 올림수(b)가 없을 때까지(b == 0) 과정을 반복한다.
4. 음수 복원: 루프가 끝난 뒤 a가 32비트 양수 범위(max_int)를 넘어가면 최상위 부호 비트가 1인 음수이므로 ~(a ^ mask)로 파이썬의 음수 정수 형태로 변환하여 반환한다.

---

복잡도 분석

• 시간 복잡도: O(1)
  • 32비트 정수 범위 내에서 자리 올림은 최대 32번만 발생하므로 루프는 최대 32회 실행된다.
• 공간 복잡도: O(1)
  • 추가적인 자료구조 없이 몇 개의 정수 변수와 마스크 상수만 사용한다.

---

구현 코드

class Solution:

    def getSum(self, a: int, b: int) -> int:
        mask = 0xFFFFFFFF
        max_int = 0x7FFFFFFF

        while b != 0:
            carry = (a & b) << 1
            a = (a ^ b) & mask
            b = carry & mask

        return a if a <= max_int else ~(a ^ mask)

---

요약 및 회고

비트 연산으로 덧셈을 구현하는 과정은 전가산기(Full Adder)의 회로 구성을 소프트웨어로 재현하는 것과 같다. 파이썬 환경에서는 임의 정밀도 정수(Arbitrary-precision integers) 특성 때문에 32비트 마스킹과 2의 보수 부호 복원식을 챙겨주는 것이 핵심이다.