[Leet Code Top 100] #371. Sum of Two Integers

문제 정보

• Leet Code 문제 링크
• 난이도 : Medium

 

해결 방법

처음에는 회로도 처럼 AND, OR, XOR 게이트 등을 상요하면 구현할 수 있을 거라고 생각을 했었는데 결국 구현이 힘들어서 Discuss 탭에 있는 답안들을 참고했습니다. a & b 와 a ^ b 를 구분해서 a & b 는 Carry 로 << shift 를 해주고 그 값들을 a 와 b 에 다시 할당해서 반복적으로 연산을 하는 방식이었습니다.

소스 코드

// Leet Code
// #371. Sum of Two Integers
// Success
// Runtime: 102 ms, faster than 25.23% of JavaScript online submissions for Sum of Two Integers.
// Memory Usage: 38 MB, less than 95.68% of JavaScript online submissions for Sum of Two Integers.

function main(){
    // Input // Output
    a = 129, b = 47; // 176

    console.log(getSum(a, b));
}

/**
 * @param {number} a
 * @param {number} b
 * @return {number}
 */
 var getSum = function(a, b) {
    let carry;
    while((a & b) !== 0){
        carry = (a & b) << 1;
        a = a ^ b;
        b = carry;        
    }
    return a ^ b;
};

main();

a & b 와 a ^ b 를 구분해서 a & b 가 1인 경우는 a 와  b 둘다 1인 경우이므로 Carry 가 발생하며, << shift 를 해주고 Carry 와 a ^ b 를 a 와 b 에 다시 할당해서 반복적으로 연산을 하는 방식입니다.

 

더 알아본 내용

 // a:10000001|b:  101111|a^b:10101110|a&b:       1|carry:      10
 // a:10101110|b:      10|a^b:10101100|a&b:      10|carry:     100
 // a:10101100|b:     100|a^b:10101000|a&b:     100|carry:    1000
 // a:10101000|b:    1000|a^b:10100000|a&b:    1000|carry:   10000
const pBin = function printBinary(n){
    return n.toString(2).padStart(8);
};

var getSum = function(a, b) {
    let carry;
    
    while((a & b) !== 0){
        // divide (a & b) and (a ^ b)

        carry = (a & b) << 1;
        // (a & b) bits are carries
        // (a ^ b) bits remains
        // calc carries and remains like a, b
        console.log(`a:${pBin(a)}|b:${pBin(b)}|a^b:${pBin(a ^ b)}|a&b:${pBin(a & b)}|carry:${pBin(carry)}`);
        
        a = a ^ b;
        b = carry;
        // doesn't matter
        // b = a ^ b
        // a = carry
    }

    // if a & b === 0
    // a ^ b is same as a + b
    return a ^ b;
};

loop 안의 과정을 console log 를 찍어서 알아보았을 때 아래 이미지와 같은 작업이 반복된다는 것을 확인했습니다.

 

참고 자료

• LeetCode Top 100 Problem Selection
• LeetCode - Very detailed explanation with two code versions.  Enjoy!
• Building an ALU