10進数を2進数に変換する方法｜C++の再帰を使ったアルゴリズム解説

10進数は2進数へ変換することができます。10進数を2進数に変換するには、対象の数値が0または1になるまで2で割り続けます。そして、各ステップで得られた余りを記録しておき、それらを逆順に並べることで2進数表現が完成します。

本記事で紹介するアルゴリズムでは、再帰的なアプローチを採用します。再帰を利用することで、スタックデータ構造を明示的に実装することなく問題を解決できます。関数の再帰呼び出しは内部的にコールスタックを使用するため、この仕組みをそのまま活かして処理を行うのがポイントです。

入力と出力の例

入力:
10進数 56
出力:
2進数表現: 111000

アルゴリズム

decToBin(decimal)

入力： 10進数の整数値。

出力： 2進数表現の文字列。

開始
    もし decimal = 0 または 1 ならば
        binary文字列に decimal を挿入する
        return
    decToBin(decimal / 2) を呼び出す
    binary文字列に (decimal mod 2) を挿入する
終了

変換の手順（56の場合）

実際に「56」を変換するときの計算過程は以下の通りです。

• 56 ÷ 2 = 28 … 余り 0
• 28 ÷ 2 = 14 … 余り 0
• 14 ÷ 2 = 7 … 余り 0
• 7 ÷ 2 = 3 … 余り 1
• 3 ÷ 2 = 1 … 余り 1
• 1 に到達したら終了

余りを下から上へ読み上げると「111000」となり、これが56の2進数表現です。再帰関数は最も深い呼び出しから順に戻っていくため、余りが自然に逆順で出力される仕組みになっています。

C++での実装例

#include<iostream>
using namespace std;

void decToBin(int dec) {
    if(dec == 1 || dec == 0) {
        cout << dec;      // decが0または1ならそのまま出力
        return;
    }

    decToBin(dec/2);     // 2で割った商で再帰呼び出し
    cout << dec % 2;      // 呼び出しから戻る際に余りを出力（逆順になる）
}

main() {
    int dec;
    cout<<"Enter decimal number: "; cin >> dec;
    cout << "Binary Equivalent: "; decToBin(dec);
}

実行結果

Enter decimal number: 56
Binary Equivalent: 111000

まとめ

このように、2で割った余りを再帰の戻り順に出力するだけで、明示的なスタックなしに10進数から2進数への変換が実現できます。計算量は割り算の回数に比例し、O(log n) で非常に効率的です。再帰の動作原理を理解する練習題材としても最適なので、ぜひ手元で動かしてみてください。