C++で2つの2進数文字列を加算するプログラムの書き方

2つの2進数を表す文字列が与えられたとき、それらを加算した結果を求め、その結果を2進数の文字列として返すことを考えます。

2進数とは、0か1のいずれかで表現される数値のことです。2進数同士を足し合わせる際には、以下のような2進数特有の加算ルールに従う必要があります。

0+0 → 0
0+1 → 1
1+0 → 1
1+1 → 0（繰り上がり1）

入力例

str1 = {"11"}, str2 = {"1"}

出力例

"100"

入力例

str1 = {"110"}, str2 = {"1"}

出力例

"111"

問題を解くためのアプローチ

• 両方の文字列を末尾（最下位桁）から走査する

• 対応する桁の2進数同士を加算する

• 1と1を足した場合は、その桁を0にして繰り上がりとして1を保持する

• 最終的な結果を返す

アルゴリズム

開始
ステップ1 → 2つの文字列を加算する関数を宣言する
    string add(string a, string b)
        文字列 result を空文字列 "" で初期化
        整数 temp を 0 で初期化
        整数 size_a を a.size() - 1 に設定
        整数 size_b を b.size() - 1 に設定
        while (size_a >= 0 || size_b >= 0 || temp == 1) の間繰り返す
            temp += ((size_a >= 0)? a[size_a] - '0': 0)
            temp += ((size_b >= 0)? b[size_b] - '0': 0)
            result = char(temp % 2 + '0') + result を計算
            temp /= 2
            size_a--
            size_b--
        繰り返し終了
        result を返す
ステップ2 → main() 内で
    文字列 a = "10101"、b = "11100" を宣言
    add(a, b) を呼び出す
終了

実装例

#include<bits/stdc++.h>
using namespace std;
// 2つの文字列を加算する関数
string add(string a, string b){
    string result = "";
    int temp = 0;
    int size_a = a.size() - 1;
    int size_b = b.size() - 1;
    while (size_a >= 0 || size_b >= 0 || temp == 1){
        temp += ((size_a >= 0)? a[size_a] - '0': 0);
        temp += ((size_b >= 0)? b[size_b] - '0': 0);
        result = char(temp % 2 + '0') + result;
        temp /= 2;
        size_a--; size_b--;
    }
    return result;
}
int main(){
    string a = "10101", b="11100";
    cout<<"sum of strings are : "<<add(a, b);
    return 0;
}

出力

上記のコードを実行すると、次の出力が得られます。

sum of strings are : 110001

このアルゴリズムでは、各桁の加算結果を一時変数 temp に蓄積し、temp % 2 によって現在の桁の値を、temp / 2 によって繰り上がりの値を求めています。どちらかの文字列の走査が終わっても、繰り上がりが残っている限りループを継続することで、桁あふれのない正確な加算を実現しています。