개요
이 문제에서는 두 개의 정수가 주어지며, C 언어로 이 두 정수의 비트 연산 기반 재귀 덧셈(Bitwise Recursive Addition)을 수행하는 프로그램을 작성해야 합니다.
비트 연산으로 합을 구하는 논리는 어릴 때 손으로 숫자를 더하던 방식과 매우 유사합니다. 각 자릿수를 하나씩 더하고, 올림수(carry)가 발생하면 다음 자릿수에 더해주는 방식이죠.
여기서도 같은 원리를 적용합니다. XOR(^) 연산자로 자릿수별 합을 구하고, AND(&) 연산으로 올림수가 발생했는지 확인합니다. 올림수가 존재하면 이를 다시 결과에 더해주고, 없다면 그대로 최종 결과를 반환합니다.
이 논리는 디지털 전자공학에서 배우는 반가산기(Half-Adder)의 동작 원리와 정확히 일치합니다.
즉, a^b(XOR)로 합을 계산한 뒤, 두 수의 특정 비트가 모두 1로 설정된 경우처럼 추가적인 올림수가 전파되어야 하는지 확인하고, 필요하다면 해당 올림 비트를 결과에 반영해야 합니다.
알고리즘 단계
1단계 — a와 b의 XOR(a^b)를 계산하여 result 변수에 저장합니다.
2단계 — {(a & b) << 1} == 0 인지 확인합니다.
2.1단계 — 0과 같다면 result가 최종 결과이므로 이를 반환합니다.
2.2단계 — 0이 아니라면, a = {(a & b) << 1}, b = result로 설정한 상태로 1단계부터 다시 수행합니다(재귀 호출).
예제 코드
다음은 위 알고리즘의 동작을 보여주는 C 프로그램입니다.
#include <stdio.h>
int addNumbers(int a, int b) {
int carry = (a & b) << 1;
int result = a ^ b;
if (carry == 0)
return result;
else
return addNumbers(carry, result);
}
int main(){
int a = 54, b = 897;
printf("The sum of %d and %d using bitwise adding is %d", a, b, addNumbers(a, b));
return 0;
}
실행 결과
The sum of 54 and 897 using bitwise adding is 951
동작 설명
addNumbers 함수는 재귀적으로 호출됩니다. 먼저 XOR 연산으로 올림수를 제외한 자릿수별 합을 구하고, AND 연산 후 왼쪽 시프트(<< 1)를 통해 올림수를 한 자리 위로 이동시켜 계산합니다. 올림수가 0이 될 때까지 이 과정을 반복하며, 올림수가 0이 되는 순간의 result 값이 곧 최종 덧셈 결과가 됩니다. 예제에서는 54와 897을 더하여 951이라는 결과를 얻습니다.