JavaScriptで2つの2進数（バイナリ）文字列を加算する方法

本記事では、2つの2進数（バイナリ）文字列を受け取り、その合計を別の2進数文字列として返すJavaScript関数の実装方法を詳しく解説します。

問題の概要

例えば、次の2つの文字列が引数として渡された場合を考えてみましょう。

const str1 = "1010";
const str2 = "1011";

このとき、期待される出力は以下の通りです。

const output = '10101';

これは10進数に直すと「10 + 11 = 21」に相当し、2進数では「1010 + 1011 = 10101」という計算になります。

アプローチのポイント

単純にparseInt()で数値へ変換して足し算する方法もありますが、桁数が大きくなると浮動小数点数の精度限界により正確な結果が得られなくなる可能性があります。そこで本記事では、右端の桁（最下位ビット）から順に処理し、繰り上がり（キャリー）を管理しながら計算する手法を採用します。この方法なら、どれほど長い2進数文字列でも正確に加算できます。

コード例

const str1 = "1010";
const str2 = "1011";

const addBinary = (str1, str2) => {
    let carry = 0; // 繰り上がりを保持する変数
    const res = [];
    let l1 = str1.length, l2 = str2.length;

    // 右端の桁から順に処理
    for (let i = l1 - 1, j = l2 - 1; 0 <= i || 0 <= j; --i, --j) {
        let a = 0 <= i ? Number(str1[i]) : 0,
        b = 0 <= j ? Number(str2[j]) : 0;
        // 現在の桁の値は合計を2で割った余り
        res.push((a + b + carry) % 2);
        // 合計が1より大きければ繰り上がり発生
        carry = 1 < a + b + carry;
    };

    // 最後の繰り上がりが残っていれば先頭に追加
    if (carry){
        res.push(1);
    }
    return res.reverse().join('');
};
console.log(addBinary(str1, str2));

処理の流れを分解して理解する

1. 初期化： 繰り上がりを保持する変数carryを0で初期化し、結果を一時的に格納する配列resを用意します。
2. 各桁の計算： 両方の文字列の末尾から先頭に向かってループ処理を行います。片方の文字列が短くて対応する桁が存在しない場合は、その桁を0として扱うことで長さの違いを吸収します。
3. 繰り上がりの管理： 各桁の合計(a + b + carry)を2で割った余りが現在の桁の値になり、合計が1より大きければ次の桁への繰り上がりフラグが立ちます。
4. 最終調整： ループ終了後に繰り上がりが残っている場合は、それを結果配列に追加します。結果は下位の桁から格納されているため、reverse()で反転し、join('')で文字列に結合して返却します。

出力結果

上記のコードを実行すると、コンソールには次のように出力されます。

10101

このアルゴリズムの計算量はO(max(n, m))（nとmはそれぞれの文字列の長さ）であり、非常に効率的です。LeetCodeなどの「Add Binary」系の問題にもそのまま応用できる定番のテクニックなので、ぜひ覚えておきましょう。