2進数を10進数に変換するDouble Dabbleの説明を試みる

2進数を10進数に変換する方法を調べました。

まえがき

普段プログラムを書いてても2進数を10進数に変換する処理はライブラリ等に隠蔽されており、意識することはありません。コンピュータ内部での数値計算は2進数ですが、それを画面などにテキストで出力するときにはプログラマも意識することなく当たり前のように10進数で出力できます。逆に2進数や16進数のまま出力する方法のほうがレファレンスを見ないとわからないぐらい。でもコンピュータの中でなんらかの方法で変換処理しているはずです。

最初に考えたのは、10進数の下の桁から導出する以下のような方法でした。2進数で表現された整数をnとします。

1. nを10で割った余りを求め、それを10進数の一番下の位とする
2. 10で割った値（端数切捨て）を求め、それを新たなnとする
3. 1に戻る ※手順1の「10進数の一番下の位」は十の位、百の位の順に読み替えていく

CPUのような0と1しかわからないデバイスにとって加減算やビット演算に比べると割り算はとても重たい処理です。もっと軽い演算で10進数に変換する方法があるはずだと思って調べたら Double Dabble という方法が見つかりました。

Double Dabbleの手順はわかったのですが、この方法でなぜ10進数に変換できるのかが私はなかなか理解できませんでした。いろんな数字での変換処理を脳内実行してみてやっと理屈がわかりました。

私の今回の記事では、直感的な変換手順を合理化すると Double Dabble に行きつくことを説明します。

この記事での10進数への変換とは、正確には2進化10進数への変換を指します。2進化10進数とは、10進数の各桁を4桁の2進数で表現することです。コンピュータの中で2進数を10進数に変換しようにも0と1しか扱えないCPUでは10進数を出力することができませんので、2進化10進数を使います。たとえば10進数で15という数字は2進数で 1111 ですが、これを2進化10進数にすると 0001 0101 になります。

2023/01/06追記
記事の投稿順序が前後しましたが、最初は10進数を導出する方法として10で割っていく上記方法を前提として効率的に10で割る方法がないかと考え、こんなことを調べていました。

本編

まずは2進数を上の桁から順番にたどって10進数にする方法を説明します。この方法を実行するのは主体は、10進数の演算ができるもの（コンピュータではなく人間）とします。

例題
2進数で10110011110（16進数で59E）は10進数で1438になります。この変換の手順を説明します。

最初に図で示します。

この手順をテキストで説明すると

1. 2進数の一番上の桁は必ず1ですが、その1を10進数の1とみなし、それより右の桁を未処理の2進数とする
2. 10進数の数字を2倍にする
3. 未処理の2進数の一番上の数字を見て、1の場合は、手順2で作成した10進数に1を加算する
4. 未処理の2進数の一番上の桁を消す
5. 未処理の2進数の桁がなくなれば終了、残っていれば手順2に戻る

この手順は10進数で演算できる人間にとっては直感的な方法です。

次に、2進化10進数（binary-coded decimal または BCD）の説明をします。

2進化10進数の演算

2進化10進数は10進数の各桁を2進数で表現したものです。10進数の1438は2進化10進数では 0001 0100 0011 1000 になります。見やすいように4桁ごとに区切りました。2進化10進数の各4桁が10進数の各桁に直接対応しています。

2進化10進数の練習問題です。

2進化10進数での
0001 0011
の2倍はなにになりますか？

10進数にすると13になり、その2倍は26です。これを2進化10進数にすると
0010 0110
になります。これはもとの0001 0011を通常の2進数と同じ要領で左に1ビットシフトしたものと一致します。次にさらにこれを2倍にするとなにになりますか？

10進数で26でしたのでその2倍は52です。これを2進化10進数にすると
0101 0010
になります。これは0010 0110の1ビットシフトとは一致しませんが、次の図のように考えると2進化10進数で直接計算できます。

1. 各桁を2倍にする。2進化10進数では左1ビットシフトする
2. 10以上になった桁があれば繰り上がりが必要なので、まずは繰り上がり先となる桁に1を加算する
3. 10以上になった桁から10を減算する。2進化10進数では1010を減算する

次は、2進化10進数での0010 1001、10進数での29の2倍を計算します。

同じ方法で計算すると次のようになります。さきほどと違うのは2倍（左1ビットシフト）したときに2進数では5桁になってしまう点です。それでも同じ方法で計算できます。

この2つのケースを2進化10進数のほうだけ並べます。

10以上となっていた桁の繰り上げ処理として先に上位に1を加算してから10を減算していましたが、これを逆順にすると、次のような手順になります。

1. 各桁を左1ビットシフトする
2. 10以上(2進数で1010以上)になった桁があれば繰り上がりが必要なので、まずはその桁から10を減算する
3. 繰り上がり先となる桁に1を加算する

実質的に同じ変換処理の手順を少しずつ書き換える作業を繰り返します。

次は10を減算する代わりに補数である6を加算します。4ビット2進数で10を減算するというのは6を加算し、オーバーフローを無視するのと同じだからです。

1. 各桁を左1ビットシフトする
2. 10以上(2進数で1010以上)になった桁があれば繰り上がりが必要なので、まずはその桁から6を加算する。その際にオーバーフローとなる5桁目は無視する
3. 繰り上がり先となる桁に1を加算する

最初の手順では、2倍した時に4桁に収まる場合と5桁になる場合がありましたが、この手順にすると、2倍しただけでは4桁に収まっていても6加算時に必ずオーバーフローの5桁目が現れます。逆に、2倍した時に5桁になった場合は6加算時にはオーバーフローしません。26と29の2つの例では次のようになります。

さらに都合のよいことに、繰り上がり先となる桁は2倍したあとなので、繰り上がり先1桁目が必ず0です。つまり繰り上がり先で1加算というのは、1桁目の0を1に変えることになります。そうなると、各桁を2倍して6加算する処理は5桁目を拡張しなくても初めから繰り上がり先の1桁目を使えばよいことになります。

つまりこういうことです。

手順3は、そういう処理をするのではなく、そう認識をしますというだけです。

さらに手順を簡略化できます。手順1と2を入れ替えます。手順2を1ビットシフトの前に実行するということは、「5以上の桁に3を加算」という表現に変わります。形骸化した手順3も削除します。

次は話を戻し、2進数を2進化10進数に変換する方法です。

2進数から2進化10進数に変換する手順

10進数を直接計算できる人間が2進数から10進数に変換する手順を再掲します。

1. 2進数の一番上の桁は必ず1ですが、その1を10進数の1とみなし、それより右の桁を未処理の2進数とする
2. 10進数の数字を2倍にする
3. 未処理の2進数の一番上の数字を見て、1の場合は、手順2で作成した10進数に1を加算する
4. 未処理の2進数の一番上の桁を消す
5. 未処理の2進数の桁がなくなれば終了、残っていれば手順2に戻る

この手順のうち10進数の演算をさきほど作った2進化10進数に置き換えると、次のような手順になります。

1. 2進数の一番上の桁は必ず1ですが、その1を2進化10進数の1とみなし、それより右の桁を未処理の2進数とする
2. 2進化10進数の各4桁のうち5以上のものに3を加算
3. 2進化10進数を左1ビットシフト
4. 未処理の2進数の一番上の数字を見て、1の場合は、2進化10進数に1を加算する
5. 未処理の2進数の一番上の桁を消す
6. 未処理の2進数の桁がなくなれば終了、残っていれば手順2に戻る

途中左シフトしたり、桁を消したり忙しいのですが、図にすると手順3,4,5は2進化10進数と未処理の2進数との境界線を1つ右にずらすだけというのがわかります。

境界線をずらしていく操作も実質的な演算ではないので、残る手順は次のようになります。

この図の太い四角枠は5以上だったので3加算した箇所、細い四角枠は5未満だったのでそのままとした箇所です。

一番右の桁は処理しないことに注意してください。

この手順ならば除算や乗算をすることなく簡単な論理回路のみで10進数に変換できます。

おわりに

この情報は誰の役に立つのだろう？

この記事は所属会社のBeeXのアドベントカレンダー18日目の記事です。弊社の記事はクラウド関連の記事が多いのですが、空気を読まずに低レイヤーのネタを書きました。そして、この記事は私の個人的な連載記事であるセルオートマトンによるCPU作成のうちの1つでもあります。