#この記事について
プログラミング学習の基礎づくりのため、基本情報技術者の参考書で学習したことを記録しています。
今回は、n進法についてまとめました。コンピュータでの利用を前提としているため、2進法を例としています。
##1.目次
1.目次
2.基本用語
3.加法と減法
4.シフト演算
5.乗法と除法
6.小数点を含む表現
7.誤差
##2.基本用語
###ビット(bit)
2進法における1桁分の情報。8進法なら3bit、16進法なら4bitを1桁で表すことができる。
###基数
「基本となる数」の略で、n進法におけるnを指す。
###桁の重み
n進法におけるそれぞれの位を指す。桁が1つ変わるごとに、nを累乗していった数値となる。
2進法であれば、2,4,8,16,32,64,128,256,...というように桁の重みが変わっていく。
###基数変換
すでにある進法で表記されている数値を別の進法に置き換えることをいう。
「桁の重み」で求める方法と、「整数部は乗法」「小数部は除法」で求める方法がある。
##3.加法と減法
###加法
繰り上がりのタイミングが異なるだけで、基本は10進法の時と同じ。
2進法であれば、1＋1の時点で繰り上がる。
###減法
コンピュータには加法の概念しかないため、負の数を加えることによって減法を表す。
最も単純に負の数を表す方法としては、
先頭の1bitを正負の符号とする。
残りのbitを全て反転(0と1)を入れ替える
1を加える
といった手順を踏む(2の補数表現)ものがある。
##4.シフト演算
bit列を左右にずらす操作をシフト演算という。
###論理シフト
符号を考慮せずにシフトする。
シフト後の空白には0を補うことで、元の数を2^nあるいは1/2^n倍した数を表せる。
1がはみ出した時、はみ出した方向が
左ならオーバーフロー(表せる範囲外)、右なら剰余となる。
###算術シフト
符号を考慮し、先頭1bitを固定してシフトする。
シフト後の空白を補う際に
左にシフトする場合は0を補い、
右にシフトする場合は符号bitで補う。
##5.乗法と除法
基本的に上述のシフト演算を利用して計算される。
###乗法
乗数を2^n同士の加法に置き換えてから計算する。
例えば、
27
= 2(2^2+2^1+2^0)
= 22^2 + 22^1 + 2
あとは、シフト演算を用いれば計算できる。
###除法
除法は、「いくつに分けられるか」という計算だが、
見方を変えて、「何回引くことができるか」と考えることで減法として計算する。
例えば、
15 / 3 なら、
1111 - 11 まず2進法にする
1111 - 1100 ＊計算結果が負にならない範囲で、除数を左シフトしてから引く
11 - 11 ＊繰り返し
元の数値から引けた回数は、
2^2 + 2^0 = 4 + 1
= 5
よって、商は5だとわかる。
##6.小数点を含む表現
###固定小数点数
「bit列のどの位置に小数点があるか」をあらかじめ決めておく方式。
小数点より上の位を「整数部」、下の位を「小数部」という。
###浮動小数点数
± m × n^e
このように、指数表記を用いて表す。
bit列では
±(符号) | e(指数部) | m(仮数部) |
という形式で表される。
また、仮数部で有効な桁を多く表せるように小数点を移動することを「正規化」という。
##7.誤差
実際の数値と、コンピュータで表すことのできる数値のズレを指す。
###けたあふれ誤差
コンピュータで表せる最小値や最大値を超えてしまった時に生じる誤差。
最小値を下回ることをアンダーフロー
最大値を上回ることをオーバーフローという。
###情報落ち
絶対値が大きく異なる数の加減法を行ったあと、
正規化により小さな数の部分が有効桁数からはみ出し、無かったことにされる。
###けた落ち
絶対値がほぼ等しい数の加減法を行った際に、
有効桁数が減り、信用できない桁数が増えてしまうこと。
###打ち切り誤差
完了まで待たずに計算処理を打ち切ることによって生じる誤差。
###丸め誤差
コンピュータが表現できる桁数を超えた際に、
超えた部分を四捨五入などして処理することにより生じる誤差。
#所感
拾う情報を増やしすぎてアウトプットの効率があまり良く無かったと感じる。
今後は、より覚えておきたいものに厳選して記述していくことにする。