[ leetcode 문제풀이 ] Sum of Two Integers

 https://leetcode.com/problems/sum-of-two-integers/

Sum of Two Integers - LeetCode

(Sum of Two Integers 문제는 위 링크에서 풀어보실 수 있습니다.)

 

 

< Sum of Two Integers 문제 설명 >

 

Sum of Two Integers 문제는 다음과 같다.

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

+와 - 연산자를 사용하지 않고 두 정수 a, b를 입력받아 합을 리턴하여라.

 

다음 두 가지 출력 예시가 주어졌다.

 

주어진 제한 조건은 -1000 ≤ a, b ≤ 1000 이다.

 

 

---

< Sum of Two Integers 문제 접근 >

 

우선 가장 단순한 한 자리 이진수의 덧셈을 살펴보자:

    0 + 0 → 0

    0 + 1 → 1

    1 + 0 → 1

    1 + 1 → 0, carry 1 (∵ 1 + 1 = 2 = 0 + (1 * 2^1))

 

Addition table을 나타내면 아래와 같고, 이는 XOR 게이트의 truth table과 유사하나 addition의 경우 1+1 = 10의 carry를 고려해주어야 한다는 점에서 XOR 이외의 추가적인 작업이 필요하다.

	0	1
0	0	1
1	1	10

 

Half Adder 라는 것은 bitwise operation을 이용해 덧셈을 계산하는 논리회로이다. half adder의 logic diagram과 truth table은 아래 그림과 같다.

from Wikipedia

 

이제 일반적인 경우의 덧셈을 생각해보자. carry는 최대 각 자리수 별로 한 번씩, int의 경우 32번 발생할 수 있다. 따라서, carry의 값은 왼쪽으로 1만큼 시프트 하여 sum과 half adder를 돌리는 과정을 반복하여야 한다. 이렇게 half adder을 연속적으로 사용하여 덧셈을 구현한 논리 회로를 Full Adder라 한다.

 

이 알고리즘을 코드로 나타내면 아래와 같다. (Cpp 사용)

int getSum(int a, int b) {
    int carry = a & b;
    int sum = a ^ b;
    while(carry){				// carry가 없을 때까지 실행
        int temp = carry <<1;
        carry = temp & sum;
        sum ^= temp;
    }
    return sum;
}

그러나 이렇게 하면 다음과 같은 runtime error가 발생한다.

Line 6: Char 34: runtime error: left shift of negative value -2147483648 (solution.cpp) SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior prog_joined.cpp:15:34

 

이 오류는 input에 음수가 있는 경우 나타났으며 int temp = carry << 1; 의 왼쪽 시프트 연산에서 오류가 발생하였다. 왜 그런가 하고 찾아보니 cpp에서 부호가 있는 int 이며 음수일 경우 왼쪽 시프트 연산이 well defined 되어있지 않아서 발생하는 것으로 보인다. 따라서 이는 unsigned int를 이용해 오류를 피해갈 수 있는데 코드로 나타내면 아래와 같다.

int getSum(int a, int b) {
    int carry = a & b;
    int sum = a ^ b;
    while(carry)
    {
        int temp = (carry & 0xffffffff) <<1; 	//not a problem anymore!
        carry = temp & sum;
        sum ^= temp;
    }
    return sum;
}

0xffffffff은 unsigned int로 처리되기 때문에 carry & 0xffffffff로 unsigned int를 얻게 되고 left bit shift 과정에서의 오류를 피하게 된다. 마지막으로 int temp에 대입함으로써 signed int 타입으로 돌아온다. 또 다른 방법으로는 

int temp = (carry & 0xffffffff) << 1; 대신 int temp = (uint32_t)carry << 1; 을 적용할 수 있다.

 

 

---

< Sum of Two Integers - Python Error >

 

파이썬 같은 경우에는 integer의 길이 제한이 없다. 따라서 왼쪽 비트 시프트를 반복하게 되면 무한루프에 빠질 수 있다. 이 문제를 해결하기 위해 mask라는 filter로 결과가 32비트 안에서만 나타나도록 아래와 같이 코드를 구현한다.

def getSum(self, a, b):
    """
    :type a: int
    :type b: int
    :rtype: int
    """
    mask = 0xffffffff
    while b:
        sum = (a^b) & mask
        carry = ((a&b)<<1) & mask
        a = sum
        b = carry

    if (a>>31) & 1: # If a is negative in 32 bits sense
    	return ~(a^mask)
    return a

마지막 if 문을 통해서는 결과값이 음수일 경우의 보정을 진행한다. while문의 mask를 통해서는 32비트 내에서만 '1'이 나타나도록 하였다. 이때 합이 음수인 경우 이 상태 그대로 리턴을 하게 되면 리턴 값은 32비트 이외에는 모두 0을 갖게 된다. 파이썬 int는 무한한 길이를 가지므로 음수를 표현하기 위해서는 무한한 1이 있어야 한다(0x...FFFFFFF...). 따라서 32비트 내에서의 값은 유지한 채 무한한 1을 만들어주기 위해 ~(a^mask) 코드가 나타나게 되었다.