두 정수 a와 b가 주어졌을 때, 이 두 수의 합을 구하는 것이 우리의 과제입니다. 여기서 중요한 제약 조건은 +나 - 같은 산술 연산자를 사용할 수 없다는 점입니다. 예를 들어 a = 5, b = 7이라면 결과는 12가 되어야 합니다.
해결 접근 방식
이 문제는 비트(bitwise) 논리 연산자를 활용하면 해결할 수 있습니다. 해결 과정은 다음과 같습니다.
- XOR(
^), AND(&), 왼쪽 시프트(<<) 같은 비트 연산자를 사용합니다. - b가 0이면 a를 그대로 반환합니다. 이것이 재귀 호출의 종료 조건입니다.
- 그렇지 않으면,
a ^ b(XOR은 올림수를 제외한 자리별 합)와a & b를 왼쪽으로 한 비트 시프트한 값(올림수)을 인자로 하여 합 함수를 재귀적으로 호출합니다.
동작 원리 이해하기
덧셈을 이진수 관점에서 보면 두 가지 요소로 나눌 수 있습니다.
- 자리별 합: 올림을 고려하지 않은 각 자리의 합은 XOR 연산 결과와 같습니다.
- 올림수(carry): 두 비트가 모두 1일 때 발생하는 올림은 AND 연산 후 한 자리 왼쪽 시프트로 표현됩니다.
예를 들어 5(101) + 7(111)의 경우, XOR 결과는 010(2)이고, AND 후 시프트한 값은 1010(10)입니다. 이 둘을 다시 같은 방식으로 더하면 최종적으로 12(1100)가 됩니다.
구현 예제 (Python)
다음 코드를 통해 실제 동작을 확인해 보겠습니다.
class Solution:
def getSum(self, a: int, b: int) -> int:
# b가 0이면 올림수가 없으므로 a가 곧 결과
if b == 0:
return a
# XOR: 올림수를 제외한 자리별 합
# (a & b) << 1: 올림수를 계산하여 한 자리 왼쪽으로 이동
return self.getSum(a ^ b, (a & b) << 1)
ob = Solution()
print(ob.getSum(5, 7))입력
a = 5 b = 7
출력
12
복잡도 분석
- 시간 복잡도: O(log n) — 정수의 비트 길이에 비례하여 재귀 호출이 진행됩니다.
- 공간 복잡도: O(log n) — 재귀 호출에 따른 스택 공간이 사용됩니다.
이처럼 산술 연산자 없이도 비트 연산만으로 두 정수의 합을 효율적으로 계산할 수 있습니다. 이 기법은 전자 회로의 가산기(adder) 설계 원리와도 같아서, 컴퓨터가 실제로 덧셈을 수행하는 방식을 이해하는 데 큰 도움이 됩니다.