PICマイコンでBCD変換 その2

以前PICマイコンでBCD変換という記事を書きました。
久しぶりにまたBCD変換を実装しなければならない場面が出てきたので、そういえば昔そんな記事書いていたよなと思って自分のブログを読み返したのですが、そこで参照していた外部サイトがリンク切れを起こしていましたので、訪れた人にとっては理解しにくい記事になってしまっていました。

ですので、そのBCD変換 のアルゴリズムをこの記事にて詳しく説明します。
もしもBCD変換の意義とかそのあたりについてを知りたい人、もしくは具体的な実装を見たい人がいれば上のリンクの記事を見てください。

準備

このようなメモリ空間を用意します。

下の位に2進数、上の位にBCD変換された数が入るようにして、一続きの値になるようにします。以前の記事では、24bit整数型と共用体でビットフィールドを作成し、このようなメモリを実現しました。

さて、実際に計算をこの箱を使いながら試していきます。
今回は例として、「123」をBCD変換してみましょう。123は2進数で表現すると0111 1011です。

n進数

n進数のおさらいです。
普段我々が日常的に使っているのは10進数で、1桁に0～9の10個の数を使います。そしてその桁の数が10を超えたら次の位に1が加算されます。つまり、各桁の値が表しているのは$10^n$ずつの単位になります。
ですので、 $10^n$の位の数字を$d_n$と置くと、各桁の値を使って以下のように表せます。\[10^0d_0+10^1d_1+^2d_2+...\]なんら疑問のない表現ですね。多くの人にとってはくどすぎる解説にすら感じるでしょう。
この考え方は2進数でも同じです。2進数で各桁の値を$b_n$と置くと、2進数の数値は以下のように表せます。\[2^0b_0+2^1b_1+2^2b_2+...\]つまり、上の2進数表現をした123は、すなわち以下のような表現だということです。\[2^7\times0+2^6\times1+2^5\times1+2^4\times1+2^3\times1+2^2\times0+2^1\times1+2^0\times1\\=64+32+16+8+2+1\]さて、話を戻して、この2進数の各桁の数から値を得る式を少し変形してみましょう。\[2^0b_0+2^1b_1+2^2b_2+2^3b_3+2^4b_4+2^5b_5+2^6b_6+2^7b_7\\=b_0+2(b_1+2(b_2+2(b_3+2(b_4+2(b_5+2(b_6+2b_7))))))\]そんなに難しい変形ではないですね。ここで重要なのは、$b_7$を2倍してから$b_6$を足して、それを丸ごと2倍してから$b_5$を足して…という計算で2進数の各桁を数値に変換できるということです。このBCD変換はこの考え方が大きなヒントになります。

左シフト

さて、先ほどの話に戻って、準備で用意したメモリを使って処理をしていきます。
これに左シフト演算を8回行います。ただ単にシフトするだけでは「2進数」エリアにある数字が「BCD10の位」「BCD1の位」の8ビット分に移動するだけですが、ここでは、この「移動するだけ」のシフト演算に意味を見出していきます。
左シフトには「値を2倍にする」という意味合いがあります。10進数で表された数の各桁を一つ左の位に移動させたら値は10倍になりますよね。同じように、2進数でも2倍になります。

BCD1の位を中心に物事を考えると、1回目の左シフトでBCD1の位の最小桁に現れた「0」（下の画像で赤色のもの）は、残り7回のシフトで最終的に$2^7$がかかります。2回目のシフトで現れた「1」（下の画像で緑色のもの）は、残り6回のシフトで最終的に$2^6$がかかります。

このように、左シフトを1回ずつしながら値を動かしていくことで「2進数の各桁の値を倍々にしていって、各桁にふさわしい係数（$2^n$）がかかるようにする」という操作をしているとみなすことができます。これは、先ほどの各桁の数から値を導く式とやっていることは同じです。

さて、この操作、メモリ空間上でやっているので2進数でしか物事が見えていませんが、別に入れ物の数の表し方がどうであれ、「2倍して2進数の次の桁を足す」という操作さえ8回繰り返してできれば、示す数値としては元の2進数と同じ意味合いになるはずです。
ですので、左側のBCD3桁分で、BCDに沿ったルールで「2倍して2進数の次の桁を足す」という処理を行っていけば、「BCDで表される元の2進数と同じ数値」が得られるわけです。

BCDとしての「2倍する」

さて、いよいよBCD変換の肝に入っていきます。今度は4bitずつ、「BCDの位」 単位で物事を見ていきます。
前章の最後にも少し触れましたが、BCDの位単位で物事を見ようとも、「2倍してから2進数の次の桁を足す」という計算さえできれば、元の2進数と同じ意味合いの数値が得られます。

ここでBCDで2倍するとはどういうことか、考えてみます。
それは、まぎれもなく左シフトで実現できます。ただし、2進数とは違い、左シフトだけがすべてではありません。BCDの桁は4bitありますので、物理的には0000～1111(2進数)、すなわち0～15(10進数)の16個の数字が入ります。ですがBCDの桁が表すのは10進数の1桁、あくまでも入る数字は0～9です。ですので、左シフトをした後に10以上の数字が入っていたら繰り上げ処理をしてあげれば、問題なく「2倍」の数が得られるはずです。

というわけで実際にやってみましょう。
先ほどの流れで順調に左シフトをしていくと、5回目の左シフトで異変が起こります。
BCD1の位の値が「1111(2進数)」すなわち「15(10進数)」になってしまうのです。ここで桁あふれ処理として、1つ上の位に1を足して、自身は1の位の値だけを保持するという処理をしてあげます。そのシフト繰り上げ処理をしたのが以の図の下2行になります。

「左シフトを8回する過程でこんな変な処理を入れちゃっておかしくならないの？」と思う方もいるかもしれません。
しかし思い出してください。やっていることは「2進数の桁を1桁ずつ加算しては2倍するの処理を繰り返す」ということだけです。その過程で、物事の見方が2進数からBCDに切り替えているのならば、ちゃんとBCDのルールに沿って2倍する処理をしてあげればいいだけです。BCDのルールでは、「各桁の値は10以上になってはいけない」がありますので、超えてしまったらちゃんと次の桁に送ってあげればいい、それだけです。「2進数の桁を1桁ずつ加算しては2倍するの処理を繰り返す」以上のことは何もしていません。ですので、BCDの表現ルールに従ったうえでの結果にはなりますが、数値の意味としては何ら変わりません。

この調子で続けていきます。毎回シフトするたびに各桁が桁あふれしていないか確認し、桁あふれしていれば繰り上げ処理をしてあげます。

 合計8回シフトし終わった時点で、2進数の部分の数値はすべて出払い、BCDの部分には左から順に「1」「2」「3」が格納されました。このようにして、除算を一切使わずにBCD変換ができてしまうのです。

落とし穴

さて、ここまで説明してきた方法には落とし穴というか、考慮されていないパターンがありました。気づいた方はいますでしょうか。これで気づけていたらすごいと思います。

例えば「152(10進数)」=「10011000(2進数)」のBCD変換を考えてみましょう。

4回シフトした時点でBCD1の位が1001(2進数)=9(10進数)となるので、桁あふれはしていません。ですので、このまま進めて左シフトをします。
やっていることは「値を2倍して次の桁を足す」の処理なので、BCD1の位は9を2倍して18、その1はBCD10の位へ繰り上がり、残りの8に2進数のエリアからやってきた次の桁「1」が足し合わされ、9になることが期待されます。 しかし実際に入っていたのは3でした。
このまま続けていくと、最終的にBCDエリアには0001 0000 0100の値が入り、結果は「104」となってしまいます。157とは違う、間違った計算結果になってしまいました。

何が間違っていたかというと、9をそのまま左シフトしてしまったことです。
9を2倍すると桁あふれすることはわかり切っていますが、その後の結果は 「3」となっており、桁あふれを検知できません。すなわち、「BCDの桁あふれ」の章で赤字で書いた「左シフトをした後に10以上の数字が入っていたら」というのは実は間違い（条件不十分）だったわけです。桁あふれを起こしても10以上の数字が入らないことがあるんですね。

先ほども書いたように、9を2倍するということは、1つ上の桁に1が入り、自身の桁には8が入ることを意味します。しかし、単純に左シフトをしてしまうと、1つ上の位には1が入りますが、自身の桁には2が入ります。
それもそのはず、左シフトでは単なる16進数としての扱いなので、9の2倍である12(16進数)をそのまま10進数とみなしてBCD1の位に2が入ってしまっていたのです。

すなわち、従来の「左シフト（＝2倍）して10以上ならば繰り上げ処理をする」という方法では、値が8, 9のときに10以上になったことを検知できなくなってしまいます。かなり厄介です。

対策

これを防ぐにはどうしたら良いでしょう。値が8, 9のとき、次回繰り上げ処理をするようなプログラムを書く？いやいや、前回の演算が影響してくるループとかややこしくてやってられません。バグの元です。

こんな時はまるっきり見方を変えてみましょう。

「桁の値が5以上ならば次に左シフトすると桁あふれを起こすから、あらかじめ繰り上げ処理をしておこう」

これならどうでしょうか。
繰り上げ処理とは、10～15の6つの数字をスキップすることですから、10以上だった場合は6を足してあげれば良いのです。6を足せば自身の位の最上位bitが自然とあふれて1つ上の桁の最下位bitに1が足されます。
これを左シフトする前に行うのならば、6の代わりに3を足しておけば、シフト後に6を足したのと同じ計算結果になるはずです。

というわけで、方針がここまでで以下のように推移してきました。

×「桁の値が10以上ならば桁あふれを起こしているから、1つ上の桁に1を足して自身から10を引こう」←桁あふれを起こしても10以上にならないことがあるからダメ

↓

△「桁の値が10以上の場合の処理に加えて、左シフト前の桁の値が8,9のときは左シフト後に桁の値が10以上にならない桁あふれを起こすから、その場合の処理を記述しよう」←正しいが実装上の条件が複雑でよくない

↓

○「桁の値が5以上ならば次に左シフトすると桁あふれを起こすから、シフト完了後に6を足そう」←だいぶ条件がスッキリしたが、ループの前回の条件が影響するのはまだ改善の余地あり

↓

◎「桁の値が 5以上ならば次に左シフトすると桁あふれを起こすから、あらかじめ3を足しておこう」


これに従って先ほどのBCD変換をしてみます。

 先ほどは「1001だから桁あふれしていない」、シフト後は「0011だから桁あふれしていない」という判定となり、本当は桁あふれしていることに気づかずに通り過ぎてしまっていましたが、今回は「1001は5以上だから次のシフトで桁あふれする」という判断になり3を足すことができましたので、次のシフトでBCD1の位に正しく「1001(2進数)」=「9(10進数)」が入りました。

続きを見ていきましょう。

左シフトの前には必ず各桁に対して「5以上か」という判定が入り、5以上ならば3を足すことで繰り上げ処理としています。
これで、最終的に8回シフトが終わった時点で0001 0101 0010で152が得られました。めでたしめでたし。

まとめ

かなり丁寧に書きましたが、まとめるとアルゴリズムの考え方としては以下の通りです。

1. 2進数の各桁（＝bit）を2倍しては次の桁を足して…という処理をBCD上で行うことで2進数→BCD変換を行う。
2. 2倍する際にはBCDだと桁あふれが起こるため、分岐処理が必要。
3. 桁あふれしてから繰り上げ処理をしようとすると条件が複雑になるので、2倍する前に桁の値が5以上だったら3を足して繰り上げ処理とする。

アルゴリズムとしてはここまでで、これをいかに効率よく処理させるかということに関しては以前の記事にしっかり載っていますので、必要な方は参照してください。