[Leetcode] 371. Sum of Two Integers (Medium) - javascript

📝 문제

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

(+, - 연산자의 사용 없이 인자의 합을 구하시오)
 

Example 1:

Input: a = 1, b = 2
Output: 3

Example 2:

Input: a = 2, b = 3
Output: 5

Constraints:

-1000 <= a, b <= 1000

 

🤔 나의 풀이

// 1차 풀이: 직접 가산기 만들어봄 => 실패
function binaryCarculator(a, b) {

    a = a.toString(2).split('');  // 이진수로 변환 -> 배열로 변환
    b = b.toString(2).split(''); 

    let next = 0; // 올림수
    let result = ''; // 더해진 이진수 저장

    while((a.length || b.length) > 0) { // 모두 배열의 값이 사라질 때까지 반복


        // 따로 padstart로 0 채우지 않고 비어있을 경우 0으로 처리
        let [aNum, bNum] = [+(a.pop() || '0'), +(b.pop() || '0')]; 

        if((aNum && bNum) === 1) { // 둘 다 1이면

            if(next === 1) result = '1' + result; // 올림수 있다면
            else { // 올림수 없다면
                next = 1;
                result = '0' + result;
            }
        }

        else if ((aNum || bNum) === 1) { // 하나만 1이면
            if(next === 1) { // 올림수 있다면
                next = 1;
                result = '0' + result;
            }
            else result += '1';
        }

        else {
            if(next === 1) {
                next = 0;
                result = '1' + result;
            } else result += '0';
        }
    }

    // 남은 올림수 있다면 맨 앞에 넣어줌 => 이진수 반환
    return next ? next + result : result;
}

// 빼기 계산하기 => 2의 보수로 변환하는 함수
function makeTwosComplement(num) {

    let binary = num.toString(2).padStart(10, '0');
    let result = '';

    for(let s of binary) {
        if(s === '0') result += '1'
        else result += '0'
    }

    // 끝에 1을 더한 후, 숫자로 변환
    return parseInt(binaryCarculator(parseInt(result,2), 1), 2);
}

var getSum = function(a, b) {

    let result = '';

    if(a >= 0 && b >= 0) return parseInt(binaryCarculator(a,b),2);
    else if(a < 0 && b > 0) return parseInt(binaryCarculator(makeTwosComplement(-a), b).slice(1), 2);
    else if(a > 0 && b < 0) return parseInt(binaryCarculator(a, makeTwosComplement(-b)).slice(1),2);
    else -parseInt(binaryCarculator(-a, -b), 2);
};

// 2차 풀이

 

비트연산 구현해야 한다는 것을 알았지만 구현이 매우 복잡했다.
양수는 그냥 더해도 되지만, 음수는 이진수를 다시 2의 보수로 바꿔야한다.

만약 음수의 절대값이 더 크다면, 다시 나온 이진수를 2의 보수로 변환하기 전으로 바꿔야 하는 일까지...

여기서 GG를 치고 포기했다ㅠㅠ

이틀에 걸쳐서 고민했는데... discuss의 짧은 코드를 보니 허탈했다.
 

🔑 선행 요소

반가산기

참고: crash course computer science 강의

 
컴퓨터는 사람처럼 직관적으로 숫자를 계산할 수 없으니

스위치를 통해 만들어진 AND, OR, XOR 등의 불 대수를 이용해 논리회로를 만든다.

덧셈은 위와 같은 반가산기 구조를 통해 덧셈을 수행한다.

 

• 이진수를 더하는 과정
  0 + 1 일 때만 1이 됨 => XOR (값이 다른 것만 1을 반환)
   

• 올림수를 계산하는 과정
  1 + 1 일 때만 1이 올라감 => AND (값이 둘 다 1이어야 1을 반환)

비트 연산자

이런 논리회로 구조를 구현할 필요 없이 비트 연산자를 사용하면 된다.

숫자 가운데에 넣으면 알아서 이진수로 바꿔서 계산하고, 다시 숫자로 변환해준다.

🔑 모범 풀이

var getSum = function(a, b) {
      let carry;
      while((a & b) !== 0){ // 4. 올림수 계산이 필요없을 때까지 반복
          carry = (a & b) << 1; // 1. 올림수 계산
          a = a ^ b; // 2. 계산
          b = carry; // 3. 다음 루프에서 계산하도록 b를 올림수로 바꿈
      }
      return a ^ b; // 5. 올림수가 없다면 최종 계산
};

a = 5, b = 1 를 예시로 설명하겠다.

 

• a의 이진수 = 101
• b의 이진수 = 001
   

1. 일단 a & b로 올림수를 계산한다.

    

   101

   001

   -------

   001 => 올림수는 한 자릿수를 올려야 하기 때문에 << 1 실행 => 010

    

   

   이런식으로 실행됨

 

2. a ^ b 로 올림 생각하지 말고 계산

    

   101

   001

   --------

   100

 

3. 올림수를 더해야 하니 a에는 계산한 수, b에는 올림수를 넣음

4. a & b === 0 으로 올림수가 없을 때까지 반복

5. 올림수가 없다면 최종적으로 더해서 반환
    

---

참고

Leetcode discuss
crash course
물한방울 블로그