C++에서 비트 연산으로 두 개의 부호 없는 정수 더하기

부호 없는 숫자(unsigned number)는 일련의 비트(bit) 스트림으로 표현되며, 이를 이진법(binary) 형태로 나타낼 수 있습니다.

예를 들어, 십진수 54의 이진 표현은 110110입니다.

비트를 이용해 두 수를 더한다는 것은, 각 숫자의 이진 표현을 이진 덧셈 논리에 따라 더하는 것을 의미합니다.

이진 덧셈의 기본 규칙

• 0 + 0 = 0
• 1 + 0 = 1
• 0 + 1 = 1
• 1 + 1 = 0 (자릿수 올림, 즉 캐리(carry) = 1 발생)

간단한 예시를 통해 두 수의 덧셈 과정을 살펴보겠습니다.

입력: a = 21 (10101), b = 27 (11011)
출력: 48 (110000)

풀이: 10101 + 11011 = 110000 입니다. 최하위 비트(LSB)부터 시작해 한 비트씩 더하고, 캐리가 발생하면 다음 자릿수로 전파하며 계산을 진행합니다.

C++ 구현 예제 (bitset 활용)

C++에서는 bitset 컨테이너를 사용하면 정수를 고정 크기의 비트 배열처럼 다룰 수 있어, 비트 단위 덧셈 로직을 직관적으로 구현할 수 있습니다.

#include <bits/stdc++.h>
#define M 32
using namespace std;

int binAdd(bitset<M> atemp, bitset<M> btemp){
    bitset<M> ctemp;
    int carry = 0;
    for (int i = 0; i < M; i++) {
        if (atemp[i] + btemp[i] == 0){
            if (carry == 0)
                ctemp[i] = 0;
            else {
                ctemp[i] = 1;
                carry = 0;
            }
        }
        else if (atemp[i] + btemp[i] == 1){
            if (carry == 0)
                ctemp[i] = 1;
            else{
                ctemp[i] = 0;
            }
        }
        else{
            if (carry == 0){
                ctemp[i] = 0;
                carry = 1;
            }
            else{
                ctemp[i] = 1;
            }
        }
    }
    return ctemp.to_ulong();
}

int main(){
    int a = 678, b = 436;
    cout << "The sum of " << a << " and " << b << " is ";
    bitset<M> num1(a);
    bitset<M> num2(b);
    cout << binAdd(num1, num2) << endl;
}

출력 결과

The sum of 678 and 436 is 1114

XOR과 AND 연산을 이용한 더 효율적인 방법

비트 연산의 성질을 활용하면 위 코드를 훨씬 간결하게 만들 수 있습니다. XOR(^)은 캐리를 제외한 자리별 합을, AND(&)와 왼쪽 시프트(<<)는 캐리를 계산합니다. 캐리가 0이 될 때까지 이 과정을 반복하면 덧셈이 완성됩니다.

#include <iostream>
using namespace std;

unsigned int addBits(unsigned int a, unsigned int b){
    while (b != 0) {
        unsigned int carry = a & b;      // 캐리 계산
        a = a ^ b;                       // 캐리를 제외한 합
        b = carry << 1;                  // 캐리를 한 비트 왼쪽으로 이동
    }
    return a;
}

int main(){
    unsigned int a = 678, b = 436;
    cout << "The sum of " << a << " and " << b << " is " << addBits(a, b) << endl;
    return 0;
}

두 방식 모두 동일하게 1114라는 결과를 출력합니다. bitset을 이용한 방식은 이진 덧셈의 원리를 학습하기에 적합하고, XOR·AND를 이용한 방식은 코드가 간결하여 실전에서 널리 활용됩니다.