[75 LeetCode] 2 - Sum of Two Integers

[75 LeetCode]는 코딩테스트 연습을 위해 한 페이스북 개발자가 추천하는 75가지 알고리즘 문제를 풀어보는 시리즈이다.

블라인드 원문:
https://www.teamblind.com/post/New-Year-Gift---Curated-List-of-Top-75-LeetCode-Questions-to-Save-Your-Time-OaM1orEU

문제 링크: https://leetcode.com/problems/sum-of-two-integers/description/

Sum of Two Integers - LeetCode

 

+나 -연산자를 사용하지 않고 덧셈을 구현하라는 문제다.

보자마자 전공에서 배웠던 논리회로 수업이 생각났다. AND/OR 게이트를 이용해서 덧셈 및 곱셈을 할 수 있는 ALU를 만들었던 기억이 어렴풋이 난다. 바로 그 기억을 되살려 진행해보았다.

function getSum(na: number, nb: number): number {
    const limit = 1 << 31;

    let carry = 0;
    let result = 0;
    let pos = 1;

    let a = na;
    let b = nb;
    let ai = 0;
    let bi = 0;
    let r = 0;

	// a와 b를 비트 단위로 한 자리씩 읽어서 carry와 함께 연산한 결과를
    // 현재 위치에 해당하는 result의 비트에 기록한다.
    while (true) {
        ai = a & 1;
        bi = b & 1;

        r = (carry ? ~(ai ^ bi) & 1 : ai ^ bi);
        carry = carry ? ai | bi : ai & bi;
        result = r ? result | pos : result;

        if (pos === limit) {
            return result;
        }

        a = a >> 1;
        b = b >> 1;
        pos = pos << 1;
    }
};


/**
 * carry, a, b 비트 연산 결과 도출하기
 *
 * c = carry, r = result
 *
 * cab c r
 * 111 1 1
 * 110 1 0
 * 101 1 0
 * 100 0 1
 * 011 1 0
 * 010 0 1
 * 001 0 1
 * 000 0 0
 */

//  c = 1 -> a | b
//  c = 0 -> a & b
//  new_c = (c & (a | b)) | (~c & (a & b)) -> 정리
//  new_r = (c & ~(a ^ b)) | (~c & (a ^ b)) -> 정리

자바스크립트에서 기본적으로 i32를 사용하는 것 같다. 비트시프트를 32회 이상 시키면 overflow가 발생하는 것을 볼 수 있었다.
그래서 limit값을 1 << 31 (0b1000_0000_0000_0000_0000_0000_0000_0000)로 설정해주었다.
pos는 현재 비트인덱스를 나타낸다. 순회를 하며 한자리씩 왼쪽으로 이동한다.

다음 순회의 c와 r의 값은 하나하나 적어서 비트 연산식을 찾아냈다. 오랜만에 하려니 기억이 안나 쉽지 않았지만, GPT의 도움 없이 해보았다.

범위가 -2000 <= a + b <= 2000이기 때문에 2^12 범위에서만 연산을 수행해줘도 된다. (-2048 ~ 2047 범위까지 표현함.)
그 후 맨 앞의 signBit에 맞게 결과를 보여줘도 되지만, 그 방식으로 했을 때도 똑같이 빨랐다.

또한, 2진법으로 출력을 원할 때 toString(2)를 사용할 수 있는데 이게 음수에 대해서는 제대로 동작하지 않는단 것을 알았다.
(-1 >>> 0).toString(2)와 같이 unsigned bit shift left 0처리를 해줘야 비트로 출력된다.

이런 잘 안쓰는 자바스크립트 문법은 항상 헷갈리는 것 같다.

위 풀이는 상위 12퍼센트로 생각보다 빨랐는데, 가장 빠른 풀이법은 아래와 같았다.

function getSum(a: number, b: number): number {
     while(b !== 0) {
        const carry = a & b;
        a ^= b;
        b = carry << 1;
    }
    return a; 
};

아래 "풀이법에 대한 해설" 링크를 참고하면 설명이 잘 되어있다. 설명 덕분에 쉽게 이해했다.
carry: 모든 비트에 대한 carry 값들. AND 연산으로 구할 수 있다.
a: 캐리를 고려하지 않은 비트 합. XOR로 구할 수 있다.

1번째 순회:
carry와 비트합(a와 b)을 구한다.
carry는 한칸 왼쪽에 더해져야하기 때문에 왼쪽으로 이동시켜둔다.

2번째 순회:
구해둔 비트합과 carry를 더한다.
carry 도 다시 계산하여 왼쪽으로 한칸 이동 시켜둔다.

탈출 조건:
carry가 더 이상 발생하지 않아 0이면 덧셈이 종료된다.

 

참고 링크:

음수의 이진법 출력: https://stackoverflow.com/questions/16155592/negative-numbers-to-binary-string-in-javascript

비트 연산 정리: https://leetcode.com/problems/sum-of-two-integers/solutions/84278/a-summary-how-to-use-bit-manipulation-to-solve-problems-easily-and-efficiently/

풀이법에 대한 해설: https://leetcode.com/problems/sum-of-two-integers/solutions/132479/simple-explanation-on-how-to-arrive-at-the-solution/