C++でn個の2進数文字列を加算する方法

本記事では、文字列として与えられたn個の2進数（バイナリ）を加算するC++プログラムの実装方法を解説します。

最も簡単なアプローチは、各2進数文字列を10進数に変換して合計し、その結果を再び2進数に戻す方法です。しかし、ここでは変換を介さず、桁ごとの演算を手動で行うことで直接加算を実現する方法を紹介します。

まず、2つの2進数文字列を加算するための補助関数を用意します。この関数をn個の2進数に対してn-1回繰り返し呼び出すことで、すべての値の合計を求めることができます。関数の動作は以下の通りです。

アルゴリズム

addTwoBinary(bin1, bin2)

begin
    s := 0
    result は空文字列で初期化
    i := bin1 の長さ、j := bin2 の長さ
    while i >= 0 または j >= 0 または s が 1 の間、繰り返す
        もし i >= 0 ならば
            s := s + bin1[i] を数値として加算
        それ以外ならば
            s := s + 0
        終了条件
        もし j >= 0 ならば
            s := s + bin2[j] を数値として加算
        それ以外ならば
            s := s + 0
        終了条件
        result := (s mod 2) を result の先頭に連結
        s := s / 2 （繰り上がりを計算）
        i := i - 1
        j := j - 1
    done
    return result
end

このアルゴリズムでは、両方の文字列を最下位ビット（LSB）から順に走査しながら、各桁の合計を変数sに蓄積していきます。sを2で割った余りが現在の桁の値となり、sを2で割った商が次の桁への繰り上がりになります。片方の文字列が先に終わった場合や、最後に繰り上がりが残った場合も正しく処理されるよう、ループ条件に「s == 1」が含まれている点がポイントです。

実装例

#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; // 最下位ビットから走査
    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関数が2つの2進数文字列の加算を担当し、add_n_binary関数が配列内のすべての文字列に対してこの関数を順番に適用しています。初期値として空文字列から始め、1つずつ累積的に加算していく仕組みです。

出力結果

10110

入力された「1011」（11）、「10」（2）、「1001」（9）の合計は22であり、2進数表現では「10110」となるため、正しく計算できていることが確認できます。