[LeetCode] Sum of Two Integers

hzw94·2021년 5월 25일
1

ProblemSolving

목록 보기
4/9

풀이

문제 자체는 굉장히 심플하다.
두 정수를 가지고 더한 값을 return 하는 것이다.
근데 특이한점이 있다면 +, - 연산을 쓰면 안된다는 것이다.

그러면 어떻게 풀까

연산을 못하면 어떻게 풀까?

내 도메인이 임베디드라 그런지는 잘 모르겠지만, 조건을 보자마자 비트연산이 떠올랐다.
컴퓨터 구조를 공부할때 배웠던 가산기가 떠올랐고, 가산기의 연산 방식을 그대로 모방하면 될 것같다는 생각이 들었다.

그래서 가산기는 무엇인가?

실제로 컴퓨터에서 어떠한 두 숫자를 통해 더하거나 뺄 때 컴퓨터는 이러한 연산을 내부의 복수의 레지스터들이 포함된 가산기(Adder)를 통해 연산을한다.

대부분의 사람들이 알다시피 컴퓨터는 2진법을 사용한다.
그렇다면 이러한 이진법을 어떻게 Adder를 통해 연산을 하는것일까?

Adder 연산 논리 따라가기

한가지 예를 들어보자.

0011 = 3
0010 = 2

이러한 값이 있을때 그냥 우리가 아는 통념에 의해 값을 더하게 되면

0101 = 5

위의 값처럼 나오게 된다.

그러면 이제 초등수학으로 넘어갈때다.

우리는 9 + 4 = 13 이라는것을 굉장히 당연히 받아들이게 된다.
일의 자리수의 최대값인 9를 넘어가는 시점에서 십의 자리수에 +1이 되고, 그것이 되기 위해 썻던 1을 제외한 나머지 3이 더해져서 13이 되는 과정을 우리는 몸으로 알고있다.

컴퓨터의 연산에서도 마찬가지다.

아까봤던 3과 2의 덧셈 연산을 보면

0011
0010

2진수 표현법으로 볼때 2번째 자릿수를 더하면 2진수의 최대값인 1을 초과하게되고, 이때 자릿수를 올려주거나 내려주는 값이 발생하게 되는데 이러한 것을 Carry(캐리) 라고한다.

또 캐리가 발생하는 지점을 2진수 덧셈의 관점에서 보게되면 동일 자릿수에서 값을 1로 같은숫자를 가지고 있을때 발생하게 되는 것을 알수 있다.

var carry = first & second

또한 발생한 캐리의 2진수 값만 놓고 본다면

0010

인데, 추후에 연산과정을 거치고나면

0100

으로 변경하게 된다.
이것을 컴퓨터에서는 왼쪽으로 값이 Shift했다고 얘기를 한다.

또한 두 피 연산 값의 캐리를 구하기 위해 썻던 비트를 제외한 나머지 값들은 배타적 으로 값이 중첩되는 것을 확인할수 있고

코드로 표현하면

let exclusive = fisrt ^ second

와 같이 된다.

그리고 덧셈에서는 최종적으로 방금 구했던 배타적 중첩의 결과와 캐리의 결과가 더해지게 된다.
이 결과의 덧셈은 배타적 중첩 결과와 캐리의 연산이 새로운 캐리를 발생하지 않을 때 까지 반복된다.

코드로 구현하면 다음과 같다.

class Solution {
    func getSum(_ a: Int, _ b: Int) -> Int {
        var first = a
        var second = b
        while (first & second) != 0 {
            let exclusive = first ^ second
            var carry = first & second
            carry = carry << 1
            first = exclusive
            second = carry
        }
        return first | second
    }
}

이러한 구조는 Half Adder와 동일하고 논리 회로 그림을 첨부한다.

profile
볼가놈의 iOS & Swift & RxSwift & PS 저장창고

0개의 댓글