n個のバイナリ文字列の合計を求める方法｜C++での2進数加算の実装例

n個のバイナリ文字列を加算するとは？

このプログラムでは、与えられた複数のバイナリ（2進数）文字列をすべて加算します。入力としてn個のバイナリ文字列が渡され、それらを合計した結果を1つのバイナリ文字列として出力するのが目的です。

処理には通常の2進数加算のロジックを利用し、1つ目の文字列からn個目までを順番に足し合わせていくことで、最終的な結果を求めます。

入出力例

Input: "1011", "10", "1001"
Output: 10110

解説：2進数のまま加算するアプローチ

もっとも簡単な方法は、バイナリ文字列を一度10進数に変換してから加算し、その結果を再び2進数に戻すことです。しかし、ここでは変換を介さずに、2進数のまま直接加算を行う方法を紹介します。

まず、2つのバイナリ文字列を加算するためのヘルパー関数を用意します。そして、この関数をn個のバイナリ文字列に対してn-1回呼び出すことで、全体の合計を計算できます。

2進数同士の加算は、以下の手順で行います。

• 両方の文字列の末尾（最下位ビット）から順に桁を読み取る
• 各桁の値と繰り上がり（キャリー）を合計し、2で割った余りを結果の桁とする
• 2で割った商を次の桁の繰り上がりとして保持する
• どちらかの文字列に残りがある間、または繰り上がりが残っている間は処理を継続する

C++による実装例

以下は、上記のロジックをC++で実装したサンプルコードです。

#include<iostream>
using namespace std;

// 2つのバイナリ文字列を加算するヘルパー関数
string add(string b1, string b2) {
   string res = "";
   int s = 0; // 桁ごとの合計（繰り上がりを含む）
   int i = b1.length() - 1, j = b2.length() - 1;
   while (i >= 0 || j >= 0 || s == 1) {
      if(i >= 0) {
         s += b1[i] - '0';
      } else {
         s += 0;
      }
      if(j >= 0) {
         s += b2[j] - '0';
      } else {
         s += 0;
      }
      res = char(s % 2 + '0') + res;
      s /= 2; // 繰り上がりを更新
      i--; j--;
   }
   return res;
}

// n個のバイナリ文字列を順に加算する関数
string addbinary(string a[], int n) {
   string res = "";
   for (int i = 0; i < n; i++) {
      res = add(res, a[i]);
   }
   return res;
}

int main() {
   string arr[] = { "1011", "10", "1001" };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << addbinary(arr, n) << endl;
}

コードのポイント

• add関数：末尾から1桁ずつ読み取り、繰り上がりを管理しながら結果を先頭に追加していくシンプルな2進数加算の実装です。
• addbinary関数：初期値として空文字列を用意し、配列内のバイナリ文字列を1つずつ累積的に加算していきます。

まとめ

この手法の大きなメリットは、10進数への変換を行わないため、整数型の範囲を超えるような非常に長いバイナリ文字列でもオーバーフローを気にせず扱える点です。各文字列の最大長をLとすると、計算量はおおむね O(n × L) となり、効率的に動作します。ビット演算や文字列操作の基礎を学ぶ題材としても最適なので、ぜひ自分のコードでも試してみてください。