[Leetcode - Binary] Sum of two integers 풀이

문제 링크

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

 

---

풀이

이 문제에서는 +, - 연산자를 사용하지 않고 두 인자의 합을 반환하는 함수를 만들어야 한다. 문제의 조건을 확인하고 비트 연산자를 써야겠다고 생각했으나, 어떤 연산자를 써야 할까 고민했다.

 

정확한 덧셈을 위해서 Carry와 이를 제외한 합을 알아야 한다. Carry를 알기 위해 사용할 수 있는 비트 연산자는 AND이다. 둘 다 1일 때만 1이므로 AND의 결과가 1이라면 Carry가 발생했음을 알 수 있다.

 

Carry를 제외한 합은 XOR 연산자로 알 수 있다. 둘 중 하나만 1일 때 XOR의 결과가 1이기 때문이다.

 

실제로 컴퓨터가 덧셈을 AND, XOR 연산자를 통해서 한다고 한다.

 

덧셈을 실행하려면 Carry를 모두 처리해서 더 없을 때까지 로직을 반복해야 하므로, AND 연산자의 결과가 0일 때 멈춘다.

 

작성된 로직을 보면 XOR의 결과를 a에 담고, AND의 결과를 왼쪽 비트로 넘겨서 더해줘야 하므로 왼쪽으로 1bit shift 하여 b에 담는다. 즉, a는 인자로 받은 a, b의 Carry를 제외한 합을 담고, b에 a, b 합의 Carry를 담아서 더 Carry가 없을 때까지 반복한다.

 

그리고 마지막에 a XOR b를 반환하면 덧셈한 결과를 얻을 수 있다.

 

 

---

정답 코드

  var getSum = function (a, b) {
    let c;
    while ((c = a & b) != 0) {
      a = a ^ b;
      b = c << 1;
    }
    return a ^ b;
  };