C++で2つの2進数文字列を加算し、結果を文字列として返すプログラム

2つの2進数を表す文字列 a と b が与えられたとします。この2つの2進数を加算し、その合計値を同じく文字列として返す必要があります。

例えば、入力が a = "10110"、b = "10010" の場合、出力は "101000" となります。

アルゴリズム

この問題は、筆算と同じ要領で下の桁から順に足し合わせていくことで解けます。具体的な手順は以下の通りです。

• 結果を格納するための空の文字列 ret を用意する
• na := a のサイズ、nb := b のサイズ とする
• i := na - 1、j := nb - 1(各文字列の末尾のインデックス)
• 繰り上がり用の変数 carry を 0 で初期化する
• i >= 0 または j >= 0 の間、以下を繰り返す:
  • addA := (i >= 0 ならば a[i] - 文字 '0' のASCIIコード差分、そうでなければ 0)
  • addB := (j >= 0 ならば b[j] - 文字 '0' のASCIIコード差分、そうでなければ 0)
  • sum := addA + addB + carry
  • carry := sum / 2
  • sum := sum mod 2
  • ret := ret に sum を連結
  • i を 1 減らす
  • j を 1 減らす
• carry が 0 以外の場合:
  • ret := ret に carry を連結
• ret を反転する
• ret を返す

理解を深めるために、以下の実装例を見てみましょう。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string solve(string a, string b){
      string ret = "";
      int na = a.size();
      int nb = b.size();
      int i = na - 1;
      int j = nb - 1;
      int carry = 0;
      while(i >= 0 || j >= 0){
         int addA = i >= 0 ? a[i] - '0' : 0;
         int addB = j >= 0 ? b[j] - '0' : 0;
         int sum = addA + addB + carry;
         carry = sum / 2;
         sum %= 2;
         ret += to_string(sum);
         i--;
         j--;
      }
      if(carry)
         ret += to_string(carry); reverse(ret.begin(), ret.end());
         return ret;
   }
};
main(){
   string a = "10110", b = "10010"; Solution ob;
   cout << ob.solve(a, b);
}

入力

"10110","10010"

出力

101000

解説

このアルゴリズムでは、両方の文字列の最下位桁(末尾)から順に処理を進めます。文字から '0' のASCIIコードを引くことで、文字を数値(0 または 1)へ変換しています。片方の文字列が先に尽きた場合は 0 として扱うため、長さが異なる2進数同士の加算にも対応できます。

各桁の合計が 2 以上になった場合には、carry(sum / 2)として繰り上がりを次の桁へ渡し、sum を 2 で割った余りがその桁の値になります。ループ終了後も carry が残っていれば、それは最上位桁への繰り上がりなので結果に追加します。下位桁から順に結果を構築しているため、最後に文字列を反転させて正しい桁順に戻す点に注意してください。

計算量について、この手法の時間計算量は O(max(na, nb))、空間計算量も O(max(na, nb)) です(na、nb はそれぞれの文字列の長さ)。大きな2進数でもオーバーフローの心配なく安全に加算できるのが、文字列として処理する利点です。