2進数の四則演算

現在勉強している基本情報技術者試験についてまとめたものです。
自分のアウトプット用なので見やすさなどは期待しないでください。

2進数の足し算と引き算

2進数の足し算
足し算の場合は、一般的に使っている10進数と理屈は同じ。

2進数の[1111 + 101]の場合

		1	1	1	1
+			1	0	1
				1(桁上)	0
			1(桁上)	0	0
		1(桁上)	1	0	0
=	1(桁上)	0	1	0	0

2進数の引き算
コンピューターは引き算という概念を持っていない為、引く数値を負の数に変換し足し算を行う。

補数
補数には、「その桁数で最大値を得るために補う数」と「次の桁に繰り上がるために補う数」の二種類がある。

10進数の[123]の場合

同じ桁数である3桁の最大数、999にいくつ足りないかが「その桁数で最大値を得るために補う数」。
$999 - 123 = 876$(9の補数)

次の桁の最小値である1000にいくつ足りないかが「次の桁に繰り上がるために補う数」。
$1000 - 123 = 877$(10の補数)

2進数の[0011]の場合

「その桁数で最大値を得るために補う数」は、
$1111 - 0011 = 1100$(1の補数)

「次の桁に繰り上がるために補う数」は、
$10000 - 0011 = 1101$(2の補数)

この2の補数を足すことで引き算をすることができる。
2の補数は全てのビットの1と0を入れ替え、1を足すと簡単に求めることができる。

この方法を用いて実際に10進数の[5 - 3]を2進数で計算した場合、下記にようになる。
$0101(5) - 0011(3) = 0101 + (-0011)$
　　　　　　　　　$= 0101 + 1101(-3)$
　　　　　　　　　$= 10010$(4桁からあふれた分は切捨)
　　　　　　　　　$= 0010(2)$

シフト演算と掛け算割り算

シフト演算
2進数のビット列を左もしくは右にずらす操作で論理シフトと算術シフトの二種類がある。
ずらすごとに桁の重みを掛けた値になる。

論理シフト
先頭のビットが1（負数）でも0（正数）でもお構いなしに行うシフト操作。
シフトした際、元の桁からあふれた数値は消去し、空いた部分は0を補う。

2進数の[00101100]を左に2ビットシフトさせる場合

←	←	0	0	1	0	1	1	0	0	[44]
0	0	1	0	1	1	0	0	0	0	[176]

計算すると2進数の整数部2桁分の重みである4倍になっている。

左にシフトしてあふれた数値が1だった場合、そのビット数で表せる範囲を超えてしまったことになる（オーバーフロー）。
逆に右にシフトした場合だと、計算の余りとなる。

算術シフト
先頭の1ビットを符号として固定し、それ以降をシフト操作する。
基本的には論理シフトと同じだが、オーバーフローの条件が1ではなく固定した数値と違う場合になる。
また、右にシフトした時に補われる数値が、0ではなく固定した数値と同じになる。

2進数の[11100100]を右に2ビットシフトさせる場合

(1)	1	1	0	0	1	0	0	→	→	[-28]
(1)	1	1	1	1	0	0	1	0	0	[-7]

計算すると2進数の小数部2桁分の重みである1/4倍になっている

$2^n$以外の掛け算
3や7などの半端な数字の場合は$2^n$で表せる数に分解する。

7倍する場合
$x * 7 = x * (4 + 2 + 1)$
　　 $= x * (2² + 2¹ + 2⁰)$
　　 $=(x * 2²) + (x * 2¹) + x$

$2^n$以外の割り算
何回引き算ができるかを$2^n$を用いて計算する。

[15 ÷ 3]の場合
[$15 ÷ 3$]を2進数に直すと[$1111 ÷ 11$]。
割られる数(1111)を超えない範囲で割る数(11)をシフトすると[1100(2ビットシフト)]となり、その数値で引き算を行うと[$1111 - 1100 = 0011$]となる。
同じ要領で[0011]を超えな範囲で割る数(11)をシフトすることはできないので、そのままの数値で引き算を行うと[$0011 - 11 = 0$]となり引き算は終了。
元の数値から引くことのできた回数は、シフトした分を足すことで求められるので[$2^2 + 2^0 = 4 + 1 = 5$]となる。

筆算で表すと下記のようになる。

		1	0	1
11)	1	1	1	1
(2ビットシフト)	1	1
			1	1
			0
			1	1
(0ビットシフト)			1	1
				0

小数点の表し方

固定小数点数
小数点の位置をあらかじめ決めておく方法。
単純で処理も早いが汎用性がない。

浮動小数点数
符号、仮数、基数、指数を用いた指数表記で数を表す。
例えば、10進数の[0.00025]の場合、0が全て左に来るまで小数点をずらした後、その分を基数に乗算してかけるので
[$0000.25 * 10⁻³　= ±(符号)0.25(仮数)*10(基数)⁻³(指数)$]となる。
コンピューターで扱うのは2進数なので、基数は2で固定となる。

浮動小数点の正規化
限られたビット数の中でより多くの桁数を保持する為、小数点の位置を調節すること。
例えば、
[$0.012345 * 10⁻³ → 0.12345 * 10⁻⁴$]　[$0.00101 * 2⁻³ → 0.101 * 10⁻⁵$]

32ビットの浮動小数点形式
その名の通り全体が32ビットで構成されており、符号（1ビット）指数部（7ビット）仮数部（24ビット）で分けられている。
指数部は2を基数とし、負の数は2の補数で表す。

この形式を用いて10進数の[0.375]を表すには、初めに2進数に変換して[0.011]とする。
次に、正規化を行い[$0.11 * 2⁻¹$]となる。
最後に、この数値をそれぞれ当てはめると
[0(符号+)1111111(指数)11(仮数)]となる。
この時、指数部は2進数の7ビットで表すので、[-1]の場合[1(0000001)]の2の補数で[1111111]となる。

IEEE754の浮動小数点形式とバイアス値
IEEE（米国電子電気技術者協会）により規格された形式で、32ビット、64ビット、128ビットなどがある。
仮数部を[0.11]といった表記ではなく[1.1]とすることで、指数部を1ビット増やすことができる。
また、指数部にバイアスとして127を足すことで、負の数でも正の数だけで表すことができ大小関係が分かりやすくなる。

実際の指数		バイアス		指数		2進数
-127	+	127	=	0	→	00000000
0	+	127	=	127	→	01111111
128	+	127	=	255	→	11111111

この形式を用いて10進数の[0.375]を表すには、初めに2進数に変換して[0.011]とする。
次に、正規化を行い[$1.1 * 2⁻²$]となる。
最後に、この数値をそれぞれ当てはめると
[0(符号+)01111101(指数)1(仮数)]となる。
この時、指数部はバイアスを足した値になるので、
[$-2 + 127 = 125(01111101)$]となる。

誤差

無限小数
割り算をしたときに、割り切れず永遠と数が続くこと。
この数値は極力近い値で置き換えるしかない為、実際の数値とのずれが発生してしまう。

けたあふれ誤差
演算した結果が、コンピューターの扱える最大値や最小値を超えることによって生じる誤差。

例えば、8ビットの固定小数点数を2進数で表すときの最小値[10000000(-128)]から最大値の[01111111(127)]の間に入らない場合は、どちらも最大値を超えたことになりオーバーフローと呼ぶ。

逆に、下限を超えることをアンダーフローと呼び、
[0.00000・・・0001]のような限りなく0に近い値の場合、指数部を表すことができず発生する。

情報落ち
絶対値の大きな値と小さな値を加減算したとき、絶対値の小さな値が計算結果に反映されず発生する誤差。

例えば、仮数部を4桁で表す浮動小数点数があったとして、
[$0.1234 * 10^4 + 0.4321 * 10⁻⁴$]を計算する場合、
初めに指数を揃えて[$0.1234 * 10^4 + 0.000000004321 * 10^4$]となる。
これを計算すると[0.123400004321]となるが、仮数部は4桁までしか入れられないので[$0.1234 * 10^4$]という計算する前と同じ値になってしまう。

打ち切り誤差
計算処理を完了まで待たずに途中で打ち切ることによって生じる誤差。
円周率の計算など、延々と続く計算を予め決めた桁で終わらせたときなどに発生する。

桁落ち
絶対値がほぼ等しい数値同士の差を求めたときに、有効な桁数が減ることによって生じる誤差。

例えば、[$0.556 * 10^7$]と[$0.552 * 10^7$]の差は[$0.004 * 10^7$]で、正規化すると[$0.400 * 10^5$]となる。
この時、4の後ろに追加された00の部分は、元の数値が00だったという保証がないため信用できない桁が増えることになる。

丸め誤差
最小桁以下の数値を四捨五入、切り捨て、切り上げなどしたときに生じる誤差。