C++の再帰プログラムによる2進数から10進数への変換

はじめに

本記事では、2進数を表す文字列が与えられたときに、再帰（リカージョン）を用いて等価な10進数を求めるC++プログラムを解説します。

2進数を10進数に変換する基本的な方法は以下の通りです。

最下位ビット（LSB）から最上位ビット（MSB）へ向かって各桁を走査し、それぞれの桁の値に 2ⁱ（0 ≤ i ≤ 桁数）を掛け合わせて、それまでの結果に加算していきます。

入出力のシナリオ例

例1

入力 − binStr[] = "110010"

出力 − 与えられた2進数に相当する10進数：50

説明 − 110010 を10進数に変換すると次のようになります。

= 0×2⁰ + 1×2¹ + 0×2² + 0×2³ + 1×2⁴ + 1×2⁵

= 0 + 2 + 0 + 0 + 16 + 32

= 50

例2

入力 − binStr[] = "0011"

出力 − 与えられた2進数に相当する10進数：3

説明 − 0011 を10進数に変換すると次のようになります。

= 1×2⁰ + 1×2¹ + 0×2² + 0×2³

= 1 + 2 + 0 + 0

= 3

プログラムで使用するアプローチ

このアプローチでは、入力文字列とその長さを受け取る再帰関数 bintoDecimal(strBin, length) を使用します。各文字を10進数の値に変換し、2ⁱ を掛けて、それまでの結果に加算していきます。

• 2進数を格納した入力文字列 strBin[] を受け取ります。
• strlen(strBin) を使って文字列の長さを計算します。
• 関数 bintoDecimal(strBin, length) は入力を受け取り、再帰的な手法で計算した数値を返します。
• 現在見ている文字が最後の文字（LSB）であれば、その桁は 2⁰ = 1 倍と同じなので、そのまま10進数の値を返します。
• それ以外の場合は、temp = binary[i] - '0' として文字を対応する数値に変換します。
• 続いて、シフト演算 temp << len-i-1 を用いて temp に 2^len-i-1 を掛けます。
• temp = temp + bintoDecimal(binary, len, i+1) のようにして、残りの桁の計算結果を temp に加算します。
• 再帰の終端で temp を返します。
• main 関数内で計算された10進数の値を出力します。

コード例

#include<bits/stdc++.h>
using namespace std;
int bintoDecimal(char binary[],int len, int i=0){
   if (i == len-1)
   return (binary[i] - '0');

   int temp=binary[i]-'0';
   temp=temp<<len-i-1;
   temp=temp+bintoDecimal(binary,len,i+1);
   return (temp);
}
int main(){
   char strBin[] = "11010";
   int length=strlen(strBin);
   cout <<"与えられた2進数に相当する10進数: "<<bintoDecimal(strBin,length) << endl;
   return 0;
}

出力結果

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

与えられた2進数に相当する10進数: 26

まとめ

このように、再帰関数とビットシフト演算を組み合わせることで、ループ処理を使わずに簡潔に2進数から10進数への変換を実装できます。再帰の基底条件（最後の文字に到達した場合）と、各桁の重み付け（2のべき乗）を正しく扱うことがポイントです。