Algorithm 문제 : 덧셈하지 않고 덧셈하기

두 수 a, b가 주어졌을 때, 덧셈(+)을 하지 않고 두 수를 더할 수 있는 함수를 짜는 것을 요구하는 문제입니다.

이를 위해서는 기본적으로 비트 연산에 대해서 잘 알고 있어야 하는데요,
두 비트가 있을 때, XOR연산은 두 비트가 다를 때 1, 두 비트가 같을 때 0이 나오게 됩니다.
비트 두개를 더한다고 생각했을 때, 올림수를 제외한 결과 비트는 XOR연산의 결과를 따르게 됩니다.

0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 0 (올림수 1 발생)

그리고 AND연산은 올림수를 예측할 때 적합합니다. 왜냐하면 둘 다 1일 때만 1이 되기 때문입니다.
즉, XOR과 AND를 잘 쓰면 덧셈을 하지 않고 덧셈을 할 수 있습니다. (실제로 컴퓨터는 이렇게 덧셈을 합니다.)

로직은 간단합니다. Recursive한 방법으로 풀텐데요, 간단한 예를 먼저 들면,

 1111
+1110
--------
11101

그런데 여기서 11101이란 수는 0001 + 11100으로 쪼갤 수 있습니다. 무슨 말이냐면, 두 수를 XOR한 값과 AND해서 1비트 왼쪽으로 쉬프트 시킨 수와의 합이라는 말입니다. 우리는 덧셈은 쓸 수 없기 때문에 다시금 이 덧셈 함수를 XOR한 값과 AND후 1비트 왼쪽으로 쉬프트 시킨 수를 재귀하는 식으로 더할 것입니다.

그렇다면 여기서 recursive함수의 종료 조건은 무엇일까요?
아마도 올림수들, 즉 AND한 값이 0이 되는 때가 생길 것입니다. 이를 다시 표현하면, 인자인 두 수 중 하나가 0이면 다른 나머지를 리턴하면 되는 것입니다. 최종적인 결과 코드는 아래와 같습니다.

def addWithoutPlus(a, b):
    if b == 0:
        return a
    elif a == 0:
        return b
    _sum = a^b
    _carry = (a&b) << 1
    return addWithoutPlus(_sum, _carry)