C/C++에서 산술 연산자 없이 두 수를 더하는 방법

이 글에서는 +, ++, -, -- 같은 산술 연산자를 전혀 사용하지 않고 두 개의 숫자를 더하는 방법을 알아보겠습니다.

이 문제는 이진 가산기(binary adder) 논리를 활용하면 해결할 수 있습니다. 디지털 회로 설계에서 사용되는 반가산기(half adder)와 전가산기(full adder)는 한 자릿수의 이진수 두 개를 더할 수 있으며, 여러 개의 가산기를 계단식으로 연결하면 더 큰 숫자를 더하는 회로를 만들 수 있습니다.

가산기의 핵심 원리는 다음과 같습니다. 먼저 두 숫자에 대해 XOR 연산을 수행하여 자리올림(carry)을 제외한 합을 구하고, AND 연산으로 자리올림 값을 계산한 뒤 왼쪽으로 한 비트 시프트하여 더해줍니다. 이 원리를 그대로 코드로 구현하면 산술 연산자 없이도 덧셈이 가능합니다.

예제 코드

#include <iostream>
using namespace std;
int add(int a, int b) {
   while (b != 0) {         // 자리올림이 없을 때까지 반복
      int carry = a & b;    // a와 b를 AND 연산하여 자리올림 계산
      a = a ^ b;            // a와 b를 XOR 연산한 결과를 a에 저장
      b = carry << 1;       // 자리올림을 왼쪽으로 한 비트 시프트하여 b에 저장
   }
   return a;
}
int main() {
   int a, b;
   cout << "더할 두 숫자를 입력하세요: ";
   cin >> a >> b;
   cout << "결과는: " << add(a, b);
   return 0;
}

실행 결과

더할 두 숫자를 입력하세요: 56
23
결과는: 79

동작 원리 정리

위 코드의 동작 과정을 단계별로 살펴보면 다음과 같습니다.

1. XOR 연산(a ^ b): 자리올림을 고려하지 않은 부분합을 구합니다. 이진수 덧셈에서 각 비트의 합은 XOR 결과와 같기 때문입니다.

2. AND 연산(a & b): 두 비트가 모두 1인 위치에서 자리올림이 발생하므로, AND 결과가 곧 자리올림 값이 됩니다.

3. 왼쪽 시프트(carry << 1): 자리올림은 한 자리 위로 올라가야 하므로 왼쪽으로 한 비트 이동시킵니다.

4. 반복: 자리올림 값(b)이 0이 될 때까지 위 과정을 반복하면, 최종적으로 a에 두 수의 합이 저장됩니다.

이 방법은 음수도 2의 보수 표현 방식으로 저장되기 때문에 대부분의 경우 올바르게 동작한다는 장점이 있습니다.