C++에서 문자열로 주어진 n개의 이진수 더하기

이 글에서는 문자열 형태로 주어진 n개의 이진수를 더하는 프로그램을 작성하는 방법을 알아보겠습니다. 가장 간단한 방법은 이진수 문자열을 10진수로 변환한 뒤 모두 더하고, 그 결과를 다시 이진수로 변환하는 것입니다. 하지만 여기서는 변환 과정 없이 덧셈을 직접 구현해 보겠습니다.

먼저 두 개의 이진수 문자열을 더하는 헬퍼 함수를 하나 만듭니다. 이 함수는 서로 다른 n개의 이진수 문자열에 대해 총 n-1번 호출되며, 내부 동작 방식은 아래와 같습니다.

알고리즘

addTwoBinary(bin1, bin2)

begin
    s := 0
    result는 현재 빈 문자열
    i := bin1의 길이, j := bin2의 길이
    while i >= 0 OR j >= 0 OR s가 1인 동안 반복:
        if i >= 0 then,
            s := s + bin1[i]를 숫자로 변환한 값
        else
            s := s + 0
        end if
        if j >= 0 then,
            s := s + bin2[j]를 숫자로 변환한 값
        else
            s := s + 0
        end if
        result := (s mod 2)를 result 앞에 연결
        s := s / 2   // 올림수(carry) 계산
        i := i - 1
        j := j - 1
    done
    return result
end

핵심 아이디어는 최하위 비트(LSB)부터 한 자리씩 살펴보면서 자리별 합을 계산하고, 2로 나눈 나머지를 결과 비트로 삼으며 몫을 올림수로 넘기는 것입니다. 이는 우리가 손으로 이진수 덧셈을 하는 방식과 정확히 같습니다. 두 문자열의 길이가 다르거나 마지막에 올림수가 남는 경우까지 반복 조건에 포함시켜 처리합니다.

예제 코드

#include<iostream>
using namespace std;
string addTwoBinary(string bin1, string bin2) {
    string result = "";
    int s = 0; //s는 비트의 합을 저장하는 데 사용됨
    int i = bin1.length() - 1, j = bin2.length() - 1; //LSB부터 탐색
    while (i >= 0 || j >= 0 || s == 1) {
        if(i >= 0)
            s += bin1[i] - '0';
        else
            s += 0;
        if(j >= 0)
            s += bin2[j] - '0';
        else
            s += 0;
        result = char(s % 2 + '0') + result;
        s /= 2; //올림수 계산
        i--; j--;
    }
    return result;
}
string add_n_binary(string arr[], int n) {
    string result = "";
    for (int i = 0; i < n; i++)
        result = addTwoBinary(result, arr[i]);
    return result;
}
main() {
    string arr[] = { "1011", "10", "1001" };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << add_n_binary(arr, n) << endl;
}

addTwoBinary 함수는 두 이진수 문자열을 받아 LSB부터 차례대로 더한 결과를 반환합니다. add_n_binary 함수는 이 헬퍼 함수를 반복적으로 호출하여 배열에 담긴 n개의 이진수를 하나씩 누적해서 더합니다. 위 예제에서는 "1011"(11), "10"(2), "1001"(9) 세 개의 이진수를 더하므로 11 + 2 + 9 = 22가 되어 이진수로 "10110"이 출력됩니다.

출력 결과

10110