non div.

つな缶が大好きな大学生。書き溜めたコードを載せていきます。

2進化十進法を使った桁数制限のない加算器(正の整数に限る)

C言語で扱える桁数は、char型だと0~255、int型だと-32768~32767、long型だと-2147483648~2147483647までしかないです。割と少ない
2進化十進法、英語だとBCD(Binary-coded decimal)という数値の表現を使って、桁数制限のない加算器をC言語でつくったので紹介します。


2進化十進法

BCDは昔の電卓(数百万円とか時代)に用いられていた数値の表現方法です。2進数4ケタ16通りで1ケタの数値(0~9)を表現しています。16通りのうち10通りしか使わないので割と勿体なかったり...しかし、ひっ算のアルゴリズムをそのままプログラムにして数値計算ができるのでわかりやすい。

BCDで数値を表現すると次のようになります。1Byteで10進数2ケタ分格納し、配列の数だけ桁数を増やすことができます。

f:id:tsunakan97:20160629232419p:plain



BCDの加算は次のように計算します。人間がひっ算で足し算をするときと同じように、下の位から順に1桁ずつ足し算を行います。

f:id:tsunakan97:20160629235502j:plain



しかし、この計算には問題があって、最上位の桁が繰り上がった時に配列の外の値に書き込みをしてしまいます。

f:id:tsunakan97:20160630004847p:plain

そのため、今回は、リトルエンディアンにしてから加算を行います。
トルエンディアンは、数値をメモリに書き込む際の順番のルールです。一般的に配列の最初のほうが大きい桁で、配列の後のほうが小さい桁がになるようにイメージすることが多いと思います。リトルエンディアンはその逆で、配列の最初のほうに小さい桁、配列の後のほうに大きい桁が来るような順番で書き込みます。最上の桁が繰り上がっても配列の次の要素に書き込めばよいです。また、こうすることで配列の最初が1桁目になり、桁数のちがう数値同士の加算でも桁をそろえることができます。

f:id:tsunakan97:20160630005016p:plain


以下、C言語で書いたABCDのソースコードと実行結果です。
BCDの解説では1Byteを2つに分けて2ケタ入れていましたが、今はメモリで困ることはないので、1Byte1桁で計算しています。贅沢!!

最後に、
関係ないですがBCDって字面がすごくきれいじゃないですか?。BCDの足し算はAddBCDで、ABCDになります!美しい!

f:id:tsunakan97:20160630005801p:plain


桁数制限のない加算器(正の整数のみ)