3.4 ビット演算子、シフト演算子

さらに、「コラム：ブール代数」で紹介したブール代数を使って、加算回路をソフトウェアでシミュレーションするプログラムを作ってみる。
今回はコンテンツの分量が多く、計算式も多いが、加算回路は高校情報Iの学習範囲であり、基本情報技術者試験の出題範囲という、コンピュータ技術では欠かせない単元なので、ぜひ習得してほしい。

（2024年7月20日）docstringをGoogleスタイルに変更．

1. サンプル・プログラム
2. ビットとバイト
3. 2進数と10進数の変換
4. 10進数と2進数、8進数、16進数
5. 2のべき乗
6. ビット論理積
7. ビット演算子と真理値表
8. シフト演算子
9. 半加算回路
10. 全加算回路
11. 練習問題
12. 次回予告
13. コラム：算数とN進数
14. コラム：キロ、メガ、ギガ
15. コラム：加算と乗算とシフト演算

ダウンロード

一般に2進数N桁は、 \( 2^N \) 種類の値を表すことができる。
8ビットを 1 バイト（byte）と呼ぶ。
1バイトは8ビットだから、 \( 2^8=256 \)種類の値を表現することができる。

Python の組み込み関数 bin関数を使うと、10進数を2進数に変換することができる。変換結果（戻り値）は文字列である。
表示する文字列を見れば分かるとおり、Python では "0b..." ではじまる数字を2進数と見なす。

# 10進数→2進数変換
a = 18			# 10進数
b = bin(a)		# 戻り値は文字列
print(b)

変数 a に代入する10進数を変えてみてほしい。

逆に、2進数を10進数に変換する筆算法を振り返っておこう。
2のべき乗を使い

\( 010010_{(2)}=2^5 \times 0 + 2^4 \times 1 + 2^3 \times 0 + 2^2 \times 0 + 2^1 \times 1 + 2^0 \times 0 = 18_{(10)} \)

と計算する。

Python のプログラムは簡単だ。2進数を代入した変数 a を、そのまま print文に渡せば10進数で表示する。

# 2進数→10進数変換
a = 0b10010		# 2進数
print(a)

変数 a に代入する2進数を変えてみてほしい。

Python の整数は、10進数、2進数のほかに、8進数、16進数で表記することができる。

2進数表記は \( 0b \) ではじめる。b は binary（2進数）の頭文字だ。前述のように、コンピュータ内部ではデータは2進数として保持されていることから、そうしたハードウェア寄りの場面で2進数を使うことは多い。
8進数表記は \( 0o \) ではじめる。o は octal（8進数）の頭文字だ。現在、プログラミングで8進数表記を使うことは滅多にないのだが、かつてのメインフレームでは、今と違ってデータの長さが36ビットであったため、それを区切りよく表現できる8進数が使われたという歴史的経緯があり、仕様に残っている。
16進数表記は \( 0x \) ではじめる。h は hexa（16進数）から x をとっている。前述のように1バイトは8ビットであるから、16進数の1桁で表現することができ都合がいい。文字コードなどバイト列を表記するときには、16進数がよく使われる。

10進数を8進数に変換する組み込み関数 oct関数や、16進数に変換する組み込み関数 hex関数を使ったプログラムを作ってみる。

# 10進数→2進数変換
a = 18			# 10進数
b = bin(a)		# 戻り値は文字列
print(b)

# 10進数→8進数変換
b = oct(a)		# 戻り値は文字列
print(b)

# 10進数→8進数変換
b = hex(a)		# 戻り値は文字列
print(b)

変数 a に代入する10進数を変えてみてほしい。

# 2進数、8進数、10進数、16進数が混在した計算
a = 0b10010 + 0o22 + 18 + 0x12;
print(a)

2進数、8進数、10進数、16進数が混在した計算もできる。結果は10進数になる。

なぜ2進数、8進数、16進数が必要かというと、冒頭に紹介したように、コンピュータ内部では2進数で処理しているためだ。とくに IoT機器のセンサー類と通信するとき、センサーデータが2進数として渡されることが多い。Python は IoT機器のソフトウェア開発で使われるシーンが多く、2進数を使う機会が多い。
センサーデータがひとかたまりになっている――たとえば3ビットデータであれば8進数が、4ビットデータであれば16進数を使う。また、5ビット以上のデータは、16進数2桁以上で表記することが多い。

プログラムを作っているときに、10進数⇔2進数変換が必要になる場面がよくある。電卓アプリで計算してもいいのだが、ある程度の数字は暗算できた方が便利である。下表の値は覚えておきたい。

べき乗	10進数
1	2
2	4
3	8
4	16
8	256
10	1,024
12	4,096
14	16,384
16	65,536

64ビット・パソコンは、CPUが一度に扱える値が64ビットあるという意味である。64ビットというと、10進数に直すと 18,446,744,073,709,551,616（1844京6744兆737億955万1616）種類の値を扱えることになる。

ここでは話を簡単にするため、下表のパラメータのみを指定できるものとする。

文字装飾

文字装飾	取り得る値
ボールド	ON / OFF
イタリック	ON / OFF
下線	ON / OFF

文字装飾の1つ1つの項目に変数を割り当ててもいいのだが、文字数の3倍もの変数が必要になってしまう（後述するリストを使うことで実現は可能だが）。

上表をもう一度見てみよう。
文字装飾の情報量は、それほど多くない。ボールド、イタリック、取り消し線は2値だから、各々の情報量は1ビット。3つでも、わずか3ビットである。これは1つの変数に押し込めることを考えてみよう。

文字装飾

	下線 第3ビット 0b100	イタリック 第2ビット 0b010	ボールド 第1ビット 0b001
ON	1	1	1
OFF	0	0	0

# 文字属性（エスケープシーケンス）
BOLD      = '\033[1m'	# 太字
ITALIC    = '\033[3m'	# イタリック
UNDERLINE = '\033[4m'	# 下線
ESC_END   = '\033[0m'	# 終了

# 初期値
attrBits = 0b101			# 文字属性ビット列
esc = ""					# エスケープシーケンスを格納する
str = "こんにちは"			# 表示文字列

# ビット判定
if (attrBits & 0b001):		# 太字かどうか
	esc += BOLD
if (attrBits & 0b010):		# イタリックかどうか
	esc += ITALIC
if (attrBits & 0b100):		# 下線かどうか
	esc += UNDERLINE

# 画面に表示する．
print(esc + str + ESC_END)

あらかじめ変数 attribute に文字属性を代入しておく。
if文 の中でビット論理積 & を使い、目的のビットが1かどうかを（立っているかどうかを）判定し、ビットが立っていれば対応するエスケープシーケンスを追加する。
最後に、作成したエスケープシーケンスと文字列を画面に表示する。

ビット演算子のオペランドは1ビット単位だ。オペランドとビット演算結果を一覧にしたものを真理値表と呼ぶ。

真理値表

A	B	A & B ビット論理積	A | B ビット論理和	A ^ B ビット排他的論理和	~A ビット反転
0	0	0	0	0	1
0	1	0	1	1	0
1	0	0	1	1	1
1	1	1	1	0	0

Python には、シフト演算子として、左シフトと右シフトを用意している。8ビット・データに対してシフト演算を行うイメージを下図に示す。

シフト演算の例題として、RGBカラーコード（#ではじまる3バイトの値）の補色を計算するプログラムを作ってみよう。前述のビット演算も組み合わせて使うことになる。
なお、補色とは、色相環の180度反対側に位置する2色のことで、補色の組み合わせは互いの色を引き立て合う相乗効果がある。また、補色を混ぜると白色になる。

補色は次の計算式によって求めることができる。R₀，G₀，B₀は元のカラーコード、R₁，G₁，B₁は補色カラーコードを意味する。max(r,g,b)はr,g,bの最大値を、min(r,g,b)はr,g,bの最小値を求める関数である。
\[ \begin{eqnarray}
MAX &=& max(R_0,G_0,B_0) \\
MIN &=& min(R_0,G_0,B_0) \\
C &=& MAX + MIN \\
R_1 &=& C - R_0 \\
G_1 &=& C - G_0 \\
B_1 &=& C - B_0
\end{eqnarray} \]

def getComplementaryColor(rgb):
	"""補色を求める
	
	Args:
		rgb(int): RGBコード
	
	Returns:
		int: 補色のRGBカラーコード
	"""

	# 元のRGBコード
	red = rgb & 0xFF0000;		# 赤
	red = red >> 16;			# 右シフトで8bit化
	green = rgb & 0x00FF00;		# 緑
	green = green >> 8;			# 右シフトで8bit化
	blue = rgb & 0x0000FF;		# 青

	# 補色のRGBコード
	cmax = max(red, green, blue);
	cmin = min(red, green, blue);
	cc = cmin + cmax;
	red1   = cc - red;
	green1 = cc - green;
	blue1  = cc - blue;
	complement = (red1 << 16) | (green1 << 8) | blue1;	#左シフト

	return complement

プログラム "complementaryColor.py" のうち、ユーザー定義関数 getComplementaryColor が補色を求めるもので、上述の計算式をそのまま Python プログラムとして書いた。
前処理として、引数 rgb は3バイト＝24ビットの整数で、上位23～16ビットがR（Red）、15～8ビットがG（Green）、7～0ビットがB（Blue）に該当するから、ビット論理積子と右シフト演算子を使って、変数 red, green, blue に分解してから補色への変換計算を行う。
最後に、左シフト演算子を使って、3バイトの整数（RGBコード）に合算する。

# メイン・プログラム ========================================================
# キーボードから入力する（文字列）
rgbStr = input("RGB = #")

# 入力バリデーション＋int変換
(response, rgb) = rgb2int(rgbStr)
if (response == False):
	dispErrorMessageAndExit(rgbStr + "は16進RGBコードではありません")

# 補色に変換する
complement = getComplementaryColor(rgb)

# 16進文字列に変換する
complementHex = hex(complement)[2:]		# プレフィックスを除いて16進数へ
complementHex = complementHex.upper()	# 英大文字にする

# 画面に表示する．
print("補色 = #" + complementHex)

メイン・プログラムは、入力バリデーション、補色変換、16進文字列への変換の順に行う。
hex関数を使って得られる16進文字列が英小文字なので、upperメソッドを使って英大文字に変換する。uppderメソッドは、文字列.uppert() のようにして使うことで、その文字列を英大文字に変換する。Python のメソッドについては追って解説する。

def rgb2int(rgb):
	"""16進RGBコードかどうかを判定し，整数に変換する．
	
	Args:
		str(str): RGBコード
	
	Returns:
		bool: 変換成功/失敗, int: 変換結果
	"""
	# 16進数整数変換してみる
	try:
		int(rgb, 16)
	# 失敗したらFalseを返す．
	except ValueError:
		return False, 0
	# 成功したら3バイトに収まっているかどうかを判定する．
	else:
		c = int(rgb, 16)
		return (c >= 0x000000) and (c <= 0xFFFFFF), c

入力バリデーションを行うのはユーザー定義関数 rgb2int だ。
以前に作成した str2int をアレンジして使っている。Pythonの組み込み関数 int関数:blue は、第2引数を指定することで、N進数の変換ができる。
RGBコードは3バイトの範囲なので、最後に比較演算子を使って最小値・最大値のバリデーションを行う。

このプログラムではRGBコード＝3バイト＝24ビットの値を整数として扱うが、プログラミング言語や実行環境によって、扱える最大／最小の整数が決まっていることを頭の片隅に置いてほしい。幸い、Python には事実上の最小／最大値の制約はなく、詳しくは「3.7 数値型の範囲と誤差」で解説する。

これまで学んだビット論理演算子とシフト演算子を使うことで、ビット演算しかできないコンピュータに加算回路を組み込むことができる。

1ビットの加算を真理値表で表すと、次のようになる。

1ビット加算の真理値表

A	B	A + B
0	0	0 0
0	1	0 1
1	0	0 1
1	1	1 0

筆算の計算結果は2進数2桁になるが、コンピュータは一度に1ビットしか扱うことができない。そこで、第1ビットを S（Sum；合計）、第2ビットを C（Carry；繰り上がり）という枠に分けてみると――。

1ビット加算の真理値表

A	B	A + B
		C	S
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	0

前述のビット演算子の真理値表を見比べてほしい。C がビット論理積 & と同じ、S がビット排他的論理和 ^ と同じになっていることが分かるだろう。
つまり、ビット論理積とビット排他的論理和を使って、1ビットの加算回路を組むことができる。これを回路図にしたものを半加算回路と呼ぶ。

半加算回路では1ビットの加算しかできない。より大きな数の加算ができるようにするためには、下の桁で発生した C（Carry；繰り上がり）を入力できる回路が必要だ。これを全加算回路と呼ぶ。

これらの加算回路を Python を使ってソフトウェア的にシミュレーションするプログラムが "addCircuit.py" だ。

def halfAddCircuit(a, b):
	"""半加算回路
	
	Args:
		a(int): 加数
		b(int): 被加数
	
	Returns:
		int キャリー, int 加算結果
	"""
	c = a & b
	s = a ^ b
	return c, s

ユーザー関数 halfAddCircuit は半加算回路を、そのままプログラムにした。

def fullAddCircuit(a, b, c0):
	"""全加算回路
	
	Args:
		a(int): 加数
		b(int): 被加数
	
	Returns:
		int キャリー, int 加算結果
	"""
	(c1, s1) = halfAddCircuit(a, b)
	(c2, s)  = halfAddCircuit(s1, c0)
	c = c1 | c2
	return c, s

ユーザー関数 fullAddCircuit は全加算回路を、そのままプログラムにした。回路図の通り、半加算回路 halfAddCircuit を呼び出す。

# メイン・プログラム ========================================================
# 初期値
c = 0	# キャリー
y = 0	# 加算結果

# キーボードから入力する（文字列）
aStr = input("加　数=")
bStr = input("被加数=")

# 入力バリデーション
a = validateNumber(aStr, "加数",   INPUT_MIN, INPUT_MAX)
b = validateNumber(bStr, "被加数", INPUT_MIN, INPUT_MAX)

# 16ビット加算回路
for i in range(0, BITS_MAX):
	a1 = a & 0b01						# 加数の1ビットを取り出す
	b1 = b & 0b01						# 被加数の1ビットを取り出す
	(c, s) = fullAddCircuit(a1, b1, c)	# 全加算回路を通す
	y += (s << i)						# 加算結果に加える
	a = a >> 1							# 次のビットへ
	b = b >> 1							# 次のビットへ

# 画面に表示する．
print(y)

メイン・プログラムは「2.4 数学関数とユーザー定義関数、入力バリデーション」で作ったプログラムを改造した。
16ビットの加算ができるように、16個の全加算回路を用意する。プログラムでは、for文 を使って16回、全加算回路を通すようにした。
また、加算結果が16ビットの正の整数（0～65,535）に収まるように、加数と被加数の範囲は（0～32,767）の範囲で入力バリデーションしている。
16ビットの制約は、プログラム冒頭で変数 BITS_MAX への代入値で決まる。

次回は、代入 = について詳しく解説し、算術演算子と代入を組み合わせた代入演算子について学ぶ。また、他のプログラミング言語のようなインクリメント演算子、デクリメント演算子がないことについて触れる。

たとえば、デジカメのカタログを読んだとき、JPEG画像は、R（赤）G（緑）B（青）それぞれ8ビット階調あるから、全部で \( 8bit^3 = 256^3 = 16,777,216 \)色を表現できることが、すぐに計算できる。
さらにRAW画像になると――メーカーによって異なるが、たとえば14ビットRAW画像なら―― \( 14bit^3 = 1,6384^3 = 4,398,046,511,104 \)（約4兆3980億）色と計算できる。これは自宅の液晶ディスプレイで表現できない色数だから、現像で工夫をしなければならないという流れになる。
ICT機器を常に携行している子どもたちの世代こそ、自然に2進数の計算結果が頭に思い浮かぶような能力を身につけてほしい。

これらを搭載したビジコン社のプログラム電卓 141-PF は、プログラムを収めるROM 4001の容量が256バイトしかなかった関係で、14桁表示にとどまったが、それでも、後の8桁の電卓より大きな計算を行うことができた。

メモリICは、内部に電位を蓄えることでデータを保持する。この回路が小さくなればなるほど、同じ大きさのICでより多くのデータを保持することができるようになる。
インテルは、CPUより早くメモリICを開発しており、1969年（昭和44年）には256ビットの 1101 を、1970年（昭和45年）10月には1024ビットの 1103 を発売した。これが大成功となった。1971年（昭和46年）にはNECが1024ビットのメモリICを開発史、1973年（昭和48年）にはMOSTEKが4096ビットのDRAM（メモリICの一種）を開発する。その後、DRAMの容量は倍々ゲームで大きくなってゆく。

メモリ容量の桁数はあっという間に大きくなっていった。4096ビット＝512バイトであるが、8で割っただけでは追いつかない。そこで、3桁区切りでカンマを付ける10進数のように、2の10乗で割り算し、SI単位系の接頭辞を付けることにした。
\( 4096 \div 2^{10} = 4 \)、つまり 4096ビット＝4Kビット のように表記するようになった。
ここで注意してほしいのは、10進数と異なり1000倍毎ではなく、1024倍毎に接頭辞が付くということ。もう1つは、ビットとバイトの読み間違えに注意すること。4096ビット＝4Kビット＝0.5Kバイト となる。

接頭辞

大きさ	名  称		記号	意  味	値
250	ペタ	peta	P	ギリシャ語のpenta、5の意味。	1,125,899,906,842,624
240	テラ	tera	T	ギリシャ語のteras、怪物(monster)の意味。	1,099,511,627,776
230	ギガ	giga	G	ギリシャ語のgigas、巨人(giant)の意味	1,073,741,824
220	メガ	mega	M	ギリシャ語のmegas、大きい(great)の意味	1,048,576
210	キロ	kilo	K	ギリシャ語のchilioi、1000の意味	1,024

乗法では交換法則が成り立つから、乗数と被乗数を比較して、小さい方を乗数にする。\( 2 \times 100 = 100 \times 2 \) となり、計算回数は2回に激減する。
だが、いつもうまく行くわけではない。 \( 1025 \times 1010 \) だと、どうやっても1000回以上の計算が発生してしまう。

ここで、2のべき乗の表を思い出してほしい。被乗数が 2、4、8‥‥であれば、左シフト演算で乗算できる。そして、シフト演算回路は比較的簡単なものなので、初期の8ビットCPUにも搭載していた。
シフト演算子を使うと、 \( 1025 \times 1010 \) の計算式は
\[
\begin{align}
&1025 \times 1010 = 1010 \times 1025 = 1010 \times (1024 + 1) \\
&= 1010 \times (2^{10} + 1) = 1000 \times 2^{10} + 1010 \times 1 \\
&= (1000<<10) + 1010
\end{align}
\]
と変形することができ、10回の左シフト演算と1回の加算で済む。

これをアセンブリで書くと、計算速度は速くなるものの、単純に加算を繰り返す場合よりコードが長くなる。ソフトウェアはメモリに比べて計算速度のコストの方が高くつくから、多少長いコードは許容された。
だが、これをハードウェアに実装しようとすると、コードが長い分、回路が複雑になってしまう。逆にハードウェアは、回路の複雑さのコストの方が高くつくので、乗算回路は搭載できなかったのだ。