JavaScript에서 '+', '-', '*', '/' 연산자 없이 두 숫자의 합 구하기

두 개의 숫자 m과 n을 매개변수로 받는 JavaScript 함수 add()를 작성해야 합니다. 이 함수는 덧셈(+), 뺄셈(-), 곱셈(*), 나눗셈(/)과 같은 네 가지 기본 산술 연산자를 사용하지 않고 두 숫자의 합을 계산하여 반환해야 합니다.

이 문제는 비트 연산자를 활용하면 우아하게 해결할 수 있습니다. 핵심 아이디어는 디지털 회로의 반가산기(Half Adder) 논리를 확장한 것으로, XOR(^)과 AND(&) 연산만으로 덧셈을 구현하는 방식입니다.

예제 코드

const m = 67, n = 33;
const add = (x, y) => {
   while(y !== 0){
      let carry = x & y;
      x = x ^ y;
      y = carry << 1;
   };
   return x;
};
console.log(add(m, n));

동작 원리

이 알고리즘의 핵심은 다음 두 가지 비트 연산의 특징에 있습니다.

• XOR(^) 연산: 두 비트의 합(자리올림을 제외한 부분)을 구할 수 있습니다. 예를 들어 1^0 = 1, 1^1 = 0처럼 각 자리에서 올림수를 무시한 덧셈 결과가 됩니다.
• AND(&) 연산: 두 비트에서 자리올림(carry)이 발생하는 위치를 찾아낼 수 있습니다. 두 비트가 모두 1일 때만 결과가 1이 되므로, 올림수가 생기는 자리를 정확히 알려줍니다.

x와 y가 서로 다른 위치에만 1비트를 가지고 있다면, 단순히 x ^ y만으로도 두 수의 합이 바로 계산됩니다. 하지만 같은 위치에 1비트가 겹쳐 있는 경우에는 자리올림 처리가 필요합니다.

이때 (x & y) << 1을 사용합니다. AND 연산으로 자리올림이 발생하는 비트들을 찾은 뒤, 왼쪽 시프트(<<)를 한 번 적용해 올림수를 한 자리 위로 이동시킵니다. 그리고 이 값을 XOR 결과와 다시 더하는 과정을 자리올림이 더 이상 발생하지 않을 때까지(y가 0이 될 때까지) 반복하면 최종 합을 얻을 수 있습니다.

정리하면 알고리즘의 흐름은 다음과 같습니다.

1. carry = x & y: 자리올림이 발생하는 비트를 계산한다.
2. x = x ^ y: 자리올림을 제외한 부분합을 x에 저장한다.
3. y = carry << 1: 자리올림 값을 왼쪽으로 한 비트 이동하여 새로운 y로 설정한다.
4. y가 0이 될 때까지 위 과정을 반복하고, 최종적으로 x를 반환한다.

실행 결과

위 코드를 콘솔에서 실행하면 다음과 같은 출력을 확인할 수 있습니다.

100

m = 67, n = 33의 실제 합이 100이므로, 산술 연산자를 전혀 사용하지 않고도 정확한 덧셈 결과를 얻은 것을 알 수 있습니다. 이 기법은 면접에서 자주 등장하는 고전적인 문제로, 비트 연산의 동작 원리를 깊이 이해하고 있는지 확인하는 좋은 예제입니다.