JavaScriptで2進数の配列を加算するアルゴリズムの実装方法

この記事では、JavaScriptを使って「0」と「1」のみで構成された2進数の配列同士を加算し、その結果を新しい配列として返すアルゴリズムを解説します。

2進数の加算の基本

2進数の加算は、次の4つの基本ルールに従います。

0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 10

ポイントは「1 + 1 = 10」、つまり桁があふれたときに繰り上がり（キャリー）が発生する点です。これは、私たちが普段行う10進数の筆算と同じ考え方です。下の桁から順に足していき、合計が基数（2進数なら2）以上になったら繰り上がりを処理します。

実装すべき処理の内容

ここで求められるのは、以下のような仕様を持つJavaScript関数です。

• 引数として、「'0'」または「'1'」の文字列のみを要素に持つ配列を2つ受け取る
• 各配列を2進数の数値とみなし、対応するビット同士を右から左へ加算していく
• 計算結果を新しい配列として返す

例えば、入力が次の2つの配列だった場合を考えてみましょう。

const arr1 = ['1', '0', '1'];
const arr2 = ['1', '0', '1'];

これは「101 + 101」の計算に相当します。期待される出力は次のとおりです。

const output = ['1', '0', '1', '0'];

サンプルコード

実際のコードは以下のようになります。

const arr1 = ['1', '0', '1'];
const arr2 = ['1', '0', '1'];
const addBinary = (arr1 = [], arr2 = []) => {
    const str1 = arr1.join('');
    const str2 = arr2.join('');
    let carry = 0, temp = 0, res = '';
    for(let i = Math.max(str1.length, str2.length) - 1; i >= 0; i--){
        const el1 = +str1[i] || 0;
        const el2 = +str2[i] || 0;
        if(el1 + el2 + carry > 1){
            temp = 0;
            carry = 1;
        }else{
            temp = el1 + el2 + carry;
            carry = 0;
        };
        res = temp + res;
    };
    if(carry){
        res = carry + res;
    };
    return res.split('');
};
console.log(addBinary(arr1, arr2));

コードの解説

この関数の動作を順番に見ていきましょう。

1. 配列を文字列に変換：join('') を使って、各配列を「101」のような2進数の文字列にまとめます。これによりインデックスで1桁ずつアクセスしやすくなります。
2. 右端からループ処理： Math.max(str1.length, str2.length) で長い方の桁数を取得し、最下位ビットから上位へ向かって1桁ずつ処理します。片方の配列が短い場合でも、+str[i] || 0 の記述により存在しない桁は0として扱われるため、安全に計算できます。
3. 繰り上がりの判定： 各桁の値と前回の繰り上がり（carry）を合計した結果が1より大きい場合、その桁の結果は0となり、繰り上がりフラグを1にセットします。それ以外の場合は、合計値をそのまま結果に使い、繰り上がりを0に戻します。
4. 最上位の繰り上がり処理： ループ終了後も carry が1のまま残っていれば、それは最上位桁への繰り上がりを意味するため、結果の先頭に追加します。
5. 結果を配列化して返却： 最後に split('') で文字列を1文字ずつ分割した配列に変換して返します。

実行結果

コンソールに出力される結果は次のとおりです。

[ '1', '0', '1', '0' ]

「101 + 101 = 1010」という2進数の加算結果が、正しく配列形式で得られていることが確認できます。

まとめ

このように、2進数の加算は「繰り上がり」を正しく管理することが核心となります。文字列として桁ごとに処理することで、JavaScriptの数値型の精度制限（Number.MAX_SAFE_INTEGER）を気にせず、非常に大きな2進数同士の加算にも対応できるのがこのアプローチの大きな利点です。ビット演算やBigIntを使う方法もありますが、桁ごとの手動計算はアルゴリズムの理解にも役立つため、学習教材としてもおすすめの題材です。