補数とビット演算

■ビット

ビットとはコンピュータで扱われる情報量の最小単位のことです。
「binary digit」を略したものが語源になっているといわれています。
ビットは2進数で表現され、2進数の1桁 = 1ビットです。

■バイト

バイトとはコンピュータで扱われる情報量の単位のことです。
1バイトは8ビットであらわす事ができます。
1バイトで最大256個の状態(数値)を表現することができます。

■補数

補数とはある値に加えると一定の基準値になる値のことです。
	基準①:その桁数で最大の数
		例:10進数(基数 => 10)の場合
			5 の補数は 4
			94 の補数は 5
			800 の補数は 199

	基準②:桁が一つ繰り上がる数
		例:10進数(基数 => 10)の場合
			5 の補数は 5
			94 の補数は 6
			800 の補数は 200

もう少し詳細に書くとb進数におけるaの数を表現するのに必要な最小の桁数をnとしたとき、
	・b^n - a をb進数におけるaに対する基数の補数(bの補数)
	・b^n - a - 1 をb進数におけるaに対する減基数の補数(b - 1 の補数)
といいます。
最初に説明した基準にあてはめると基数の補数は基準②、減基数の補数は基準①になります。
2進数では基準①を「1の補数」、基準②を「2の補数」と呼んでいます。

■2進数による負の値の表現

コンピュータで2進数の負の値を表すときは符号ビットと補数を使用して表現します。
	
●符号ビット
	符号ビットとは演算領域の先頭のビットを使用し、0なら正、1なら負として扱います。
	
●補数
	2進数の負の値は絶対値の2の補数で表現します。
	2の補数は「桁が一つ繰り上がる数」です。
	例として 演算範囲4桁の2進数 0100 (10進数=>4)を負の値に変更したいと思います。

		・0100(10進数=>4)を負の値(10進数=>-4)へ変換
			0100 
			1011 <= 桁を4桁の最大値にするためビットを反転させる(1の補数)
			1100 <= 反転したビットに1を加算する(2の補数)

	0100(10進数=>4)の負の値は1100(10進数=>-4)になります。
	2進数表記なので本当に1100は負の値になっているのかわかりづらいと思います。
	なので0100と1100を足して0になることを証明したいと思います。

		・0100(10進数=>4)と1100(10進数=>-4)の足し算
			  0100
			+ 1100
			=10000
		
	計算結果により10000となりました。
	今回の演算範囲は4桁ですので5桁目の1はあふれてしまっています。
	4桁と制限をかけていますので、あふれてしまった桁は無視します。
	結果0000となり、1100は0100の負の値になっていることが証明されました。

	以下の図は演算範囲が4ビットの場合の数値表です。
		pgtheory_0009

■ビット演算

ビット演算とはひとつ、またはふたつのビットの値を操作する演算方法のことをいいます。
ビット演算には論理演算を使用します。

●AND:論理積 ( & ):
	ANDは両方のビットが1の時のみ結果が1になるビット演算です。
		例:
				1001 0010 1010
			AND	1000 0100 1010
			=	1000 0000 1010

●OR:論理和 ( | ):
	ORはどちらかのビットが1の時に結果が1になるビット演算です。
		例:
				1001 0010 1010
			OR	1000 0100 1010
			=	1001 0110 1010

●XOR:排他的論理和 ( ^ ):
	XORはどちらかのビットが1だった時のみ結果が1になるビット演算です。
		例:
				1001 0010 1010
			XOR	1000 0100 1010
			=	0001 0110 0000

●NOT:否定 ( ~ ):
	NOTはビットを反転させます。
		例:
			NOT	1001 0010 1010
			=	0110 1101 0101

以下は上記のビット演算をまとめた真理値表になります。
真理値表とは論理演算の結果をまとめた表のことです。
pgtheory_0008

■シフト演算

シフト演算とはビットを左右にずらす(シフトする)演算方法です。
	左シフトの例:
		0110 << 1 => 1100 // (<< が左シフト演算子)
	右シフトの例:
		0110 >> 1 => 0011 // (>> が右シフト演算子)

このシフト演算には大きく分けて算術シフトと論理シフトがあります。

●算術シフト
	算術シフトは、正負を考慮した数値を扱うときに使用します。
	算術左シフトでは移動によって空いた右端の桁に0を挿入します。
		算術左シフトの例:
			1110 << 1 => 1100
	
	算術右シフトでは移動によって空いた左端の桁には
	符号ビットと同じ値を挿入します。
		算術右シフトの例:
			1110 >> 1 => 1111
			0011 >> 1 => 0001

	算術シフトでは左に1つシフトすると元の値の2倍、4倍と2の累乗倍に、
	右に1つシフトするごとに元の値の1/2、1/4と1/2の累乗倍になります。


●論理シフト
	論理シフトは数値として扱うのではなく、ビットの並びとして扱います。
	論理シフトでは左右に関係なくシフトして空いた桁に0を挿入します。

		論理シフト例:
			1111 >> 1 => 0111
			1111 << 1 => 1110