Sum of Two Integers | 알고달레

LeetCode의 371번째 문제인 Sum of Two Integers를 함께 풀어보도록 하겠습니다.

문제

두 정수 a와 b가 주어졌을 때, +와 - 연산자를 사용하지 않고 두 정수의 합을 반환하시오.

예제 1

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

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

풀이 1

아니 산술 연산자를 사용하지 않고 두 정수의 합을 구하라니 정말 독특한 문제죠? 🤷‍♂️🤷‍♀️ 눈치가 빠르신 분들은 비트 연산자를 사용해서 풀어야겠다고 이미 생각하고 계신 것 같네요. 😛

덧셈을 하는데 어떤 비트 연산자를 사용할 수 있을까요? 이진수 연산을 해보면 크게 4가지 경우를 생각해볼 수 있는 것 같아요.

00 + 00 = 00
00 + 01 = 01
01 + 00 = 01
01 + 01 = 10

XOR(^) 연산자를 사용하면 얼추 비슷한 결과를 얻을 수 있는 것 같아요. 올림수(carry)가 발생했을 때 문제가 되는군요. 🤔

00 ^ 00 = 00 ✅
00 ^ 01 = 01 ✅
01 ^ 00 = 01 ✅
01 ^ 01 = 00 ❌

a ^ b = 올림수를 제외한 a와 b의 합

올림수는 따로 논리곱(&) 연산자와 좌측 쉬프트(<<) 연산자를 조합해서 구할 수 있어요.

00 & 00 << 1 = 00
00 & 01 << 1 = 00
01 & 00 << 1 = 00
01 & 01 << 1 = 10

(a & b) << 1 = a와 b를 더했을 때 올림수

자, 그럼 이 두 결과를 더하면 우리가 원하는 두 정수의 합을 얻을 수 있겠죠?

00 + 00 = (00 ^ 00) + (00 & 00 << 1) = 00 + 00 = 00
00 + 01 = (00 ^ 01) + (00 & 01 << 1) = 01 + 00 = 01
01 + 00 = (01 ^ 00) + (01 & 00 << 1) = 01 + 00 = 01
01 + 01 = (01 ^ 01) + (01 & 01 << 1) = 00 + 10 = 10

(a ^ b) + ((a & b) << 1) = a + b

앗, 그런데 여기서 까먹으면 안 되는 점이 두 결과를 더할 때도 + 연산자를 사용할 수 없다는 거에요. 따라서 이 두 결과도 다시 비트 연산자를 통해서 더해야될 것 같아요. 이 작업을 올림수가 없어질 때까지 반복하면 되겠죠?

이 알고리즘을 파이썬으로 구현해볼까요?

class Solution:
    def getSum(self, a: int, b: int) -> int:
        xor = a ^ b
        carry = (a & b) << 1
        while carry:
            xor, carry = xor ^ carry, (xor & carry) << 1
        return xor

변수 a와 b를 재활용하면 코드가 좀 더 간결해지겠죠?

class Solution:
    def getSum(self, a: int, b: int) -> int:
        while b:
            a, b = a ^ b, (a & b) << 1
        return a

이 코드는 LeetCode에서 주어진 테스트 케이스는 통과를 하지만 제출을 해보면 Time Limit Exceeded 오류가 발생할 겁니다.

이유는 바로 우리가 음수를 고려하지 않았기 때문인데요. 예를 들어, 입력으로 -1과 1이 주어지면, 첫 올림수가 2가 되고, 그 다음에는 4가 되어 영원히 0에 도달할 수 없게 됩니다.

풀이 2

어떻게 하면 입력으로 양수가 주어지든 음수가 주어지든 작동할 수 있도록 알고리즘을 개선할 수 있을까요?

파이썬의 경우, 숫자형이 32비트가 아닙니다. 따라서 32비트 마스크를 사용하도록 코드를 수정해야합니다.

class Solution:
    def getSum(self, a: int, b: int) -> int:
        mask = 0xFFFFFFFF  # 32 bit mask
        while b & mask:
            a, b = a ^ b, (a & b) << 1
        return (a & mask) if b > 0 else a

자바의 경우, 숫자형이 32비트입니다. 그래서 위에서 파이썬으로 작성한 코드를 다시 자바로만 작성해줘도 해결이 됩니다.

class Solution {
    public int getSum(int a, int b) {
        while (b != 0) {
            int carry = a & b;
            a = a ^ b;
            b = carry << 1;
        }
        return a;
    }
}

이 풀이의 시간 복잡도와 공간 복잡도는 모두 O(1)이 되는데요. 문제에서 숫자가 -1000보다 크거나 같고, 1000보다 작거나 같다는 제약 사항이 있기 때문입니다.