新卒エンジニア勉強会-bit演算

こちらの勉強会は、本形式にまとめています。
https://zenn.dev/mandenaren/books/algorithm-study

はじめに

新卒エンジニア同士で実施している勉強会の第 4 回目の記事になります。
今回のテーマは bit 演算についてです。

回	テーマ
第 1 回	二分探索
第 2 回	ソートアルゴリズム
第 3 回	暗号化
第 4 回	bit 演算
第 5 回	連想配列
第 6 回	グラフ理論

前提

今回は bit 演算を用いて簡単な計算をするプログラムを作ります。bit 演算はコンピュータの基本原理と深い関係があります。私たちがコンピュータを触る際は、当たり前のように足し算引き算掛け算割り算の命令を入力すると計算結果が返ってきますね。しかしコンピュータは根源的には物理的な電気信号の on, off という二つの情報しか扱っていません。これだけで四則演算をどのように実現しているのか？を考えるのが今回の目的です！
問題に取り掛かる前に、知っておきたい概念があるためその説明から入ります。

電気回路

コンピュータは全ての情報を電圧の高い(5v)、低い(0v)という二種類のデジタル信号のみで表しています。電気信号は回路とスイッチを使うことで流れを制御することができます。

いずれの図も左側が高電圧で右の方に電流が流れているものと捉えてください。山から川が上流 → 下流に流れているようなイメージです。
そこに何らかの操作でスイッチを on にすることを考えます。操作とは、たとえば Ctrl(command)キーと「c」を同時に入力するとコピー処理が動くといった物理的なアクションであったり、電気の入力によるスイッチの開閉等をイメージできれば良いでしょう。

一番上の図は直列回路を表します。一本の線で繋がっているため両方のスイッチが on にならないと他方に電流は流れません。これは AND 回路とも言います。これはまさに Ctrl(command)キーと「c」を同時に入力するとコピー処理が動く状況と対応していますね。
真ん中の図は並列回路を表します。分岐があるため少なくとも一方のスイッチが on になっていれば電流は他方に流れます。これは OR 回路とも言います。
一番下の図は NOT 回路です。これは高い電圧が流れてきた時は低い電圧を出力し、低い電圧が流れてきた時は高い電圧を出力します。つまり電圧の高低を反転させる働きを持ちます。内部的には下記図のよう上から常に電流を流しておいて入力がある場合は電磁石の要領でスイッチが on になるような仕組みとなっています。スイッチが on になると上から下に電流が流れるので出力に電流は流れません。逆に入力がない場合はスイッチが off となっていて、上からの電流は出力側に流れていきます。

この三つの回路のパターンが基本原理となります。これらを色々組み合わせることで様々な電流の流れのパターンを作り出すことができます。
様々な電流の流れのパターンは記号で規格化されています。それらをまとめると以下図のようになります。

たとえば、片方の入力のみがある場合に出力するような回路を XOR 回路と言います。XOR に関して上図の記号とベン図を見てみます。まず A 以外の領域かつ B に重なる場所は、右側の、中央の重なりの除いた B の領域になります。反対に B 以外の領域かつ A と重なる場所は、左側の、中央の重なりを除いた A の領域になります。つまり、A 入力の反転(NOT)と B 入力の AND 回路、B 入力の反転(NOT)と A 入力の AND 回路を作り、この二つの出力を OR 回路に繋げば良いというわけですね。

XOR 回路は下記図のように NOT, AND, OR 回路を配置することで実現できます。

bit 演算

回路によって作られる様々な電流の動きは記号化されていてプログラムで扱えるようになっています。電圧の高低は bit という単位で 1 セット分の情報として捉え、数字の 0,1 で表現されます。特に 0,1 からなる数列の、対応する位同士に任意の回路を当てるような計算方法を bit 演算と言います。出力を見て、電流が流れた、流れなかったのような情報を再度位ごとに 0,1 で保持しておくイメージです。当然、一桁のみの bit 演算をする場合は真理値表に相当します。

論理演算	演算子	例
AND 演算	&	1010 & 1100 → 1000
OR 演算	|	1010 | 1100 → 1110
XOR 演算	^	1010 ^ 1100 → 0110

2 進法とは？

0,1 を数列として並べたものを bit 列と言い、これに位の概念を乗せることで数として解釈することができるようになります。

普段私たちは 10 進法で物事を数えています。10 進法は 0~9 の十種類の数字を使用し、1 から数えて十個目の数字で桁上がりが発生し 10 となります。11, 12,,, 19, 20, ,, 99 のように増加し、桁上がりで 100(百), 1000(千)となっていきます。桁上がり直後の数字同士を比較すると、数の大きさは十倍ずつ増えていきます。

2 進法も同様に考えることができます。2 進法は 0,1 の二種類の数字を使用し、1 から数えて二個目の数字で桁上がりが発生し 10 となります。その次は 11, 100, 101, 110, 111, 1000,,,のように表記していきます。桁上がり直後の数字同士を比較すると、数の大きさは二倍ずつ増えていきます。

2 進数	10 進数
0	0
1	1
10	2
11	3
100	4
101	5
110	6
111	7
1000	8
1001	9
1010	10

10 進数における 235 は、100 x 2 + 10 x 3 + 1 x 5 のように表現できます。位の位置に応じて 10 の N 乗の数と対応しているわけです。
同様に 2 進数の場合も、下記のように位の位置に応じて 2 の N 乗の数と対応しています。

0	0	1	1	1	1	0	0
$2^7$	$2^6$	$2^5$	$2^4$	$2^3$	$2^2$	$2^1$	$2^0$

bit 列を左右に移動させる演算をシフト演算と言います。

論理演算	演算子	例
左シフト演算	<<	1010 << 2 → 101000
右シフト演算	>>	1010 >> 2 → 10

これにより、移動した分だけ位を増減させることができます。つまり、2 進数においてシフトした分だけ 2 の倍数増加したり、割られたりします。

問題 1

1 桁の 2 進数の数字 2 つが以下のように与えられます。

input

1,0

入力された二つの数字の和に関して、2 進法で計算した場合の繰り上がりと一桁目を順に出力してください。

なお、以下の条件に従ってください。

• bit 演算子を使うこと
• 計算量は問いません

テストケース

テストケースは以下四つです。例えば入力が 1,1 だった場合、1+1 で繰り上がりが発生します。そのため繰り上がり部分は 1, 一桁目は 0 となります。入力が 0,1 だった場合、繰り上がりが発生せず、一桁目は 1 となります。

input	output
0,0	0 0
0,1	0 1
1,0	0 1
1,1	1 0

コマンドラインからの入力を受け取る方法

python

# 入力
first, second = list(map(int, input().split(',')))

解答例

クリックすると解答例が見られます

# 入力
first, second = list(map(int, input().split(',')))

# 半加算器
def half_adder(a, b):
    return a & b, a ^ b

carry, sum = half_adder(first, second)
print(carry, cum)

入力された二つの数字から、繰り上がりと一桁目、それぞれどの bit 演算(回路)を当てれば良いかを考えます。
繰り上がりは、入力値が両方 1 の場合のみ 1 となるので AND 演算と対応しています。1 桁目は、入力値の片方のみが 1 となっている場合に 1 となるので XOR 演算と対応しています。(XOR 回路も元々は NOT, AND, OR 回路の組み合わせでできていましたね。)

この問題では 1bit の足し算に焦点を当てた回路を作りました。これは半加算器と呼ばれています。

問題 2

問題 1 で 1 桁目の足し算ができるようになりました。今度は 2 桁目の計算をしたいです。
2 桁目に計算する 2 進数の数字 2 つ A,B と、下からの繰り上がり C が以下のように与えられます。

input

0,1,1 # A,B,C

2 桁目の計算結果に関して、3 桁目の繰り上がりと 2 桁目の数字の計算結果を出力してください。

なお、以下の条件に従ってください。

• bit 演算子を使うこと
• 計算量は問いません

テストケース

テストケースは以下 6 つです。例えば入力が 1,1,0 の場合、下位からの繰り上がりは 0 であるため、結果として 1,1 の足し算(=半加算器)をすればよく、3 桁目の繰り上がりは 1, 2 桁目の数は 0 となります。入力が 0,1,1 の場合、下位からの繰り上がりが存在するため 2 桁目では繰り上がりと片方の入力値同士で 1,1 の足し算をすることになります。そのため、3 桁目の繰り上がりは 1, 2 桁目の数は 0 となります。入力が 0,0,1 の場合、下位からの繰り上がり分が 2 桁目の数字として落ち着きます。

input	output
0,0,0	0 0
0,1,0	0 1
1,1,0	1 0
0,0,1	0 1
0,1,1	1 0
1,1,1	1 1

コマンドラインからの入力を受け取る方法

python

# 入力
A, B, C = list(map(int, input().split(',')))

解答例

クリックすると解答例が見られます

# 入力
A, B, C = list(map(int, input().split(',')))

# 半加算器
def half_adder(a, b):
    return a & b, a ^ b

# 全加算器
def full_adder(a, b, c):
    carry1, sum1 = half_adder(a, b)
    carry2, sum2 = half_adder(sum1, c)
    carry = carry1 | carry2
    return carry, sum2

carry, sum = full_adder(A, B, C)
print(carry, sum)

まず半加算器を用いて入力値 A と B の加算を行い、その結果の和 sum1 と繰り上がり carry1 を得ます。次に、sum1 と下位からの繰り上がり C を半加算器で加算し、その結果の和 sum2 と繰り上がり carry2 を得ます。最後に、carry1 と carry2 のどちらかが 1 であれば繰り上がりが発生するため、これらを OR 演算して最終的な繰り上がり carry を得ます。

このように、下位からの繰り上がりを考慮した加算器を全加算器と呼びます。

この全加算器を下位から繰り返し再帰的に利用していくことで、2 進数での足し算を作ることができます。

これを図示すると下記のようになります。

その他のトピック

これまでの問題は 2 進数での足し算を考えてきました。では引き算や掛け算、割り算はどのように実現されるのでしょうか？

引き算

まず引き算についてです。一旦仕組みをイメージしやすくするために 10 進数で考えてみます。例えば 8 - 6 という計算を見ていきます。

引き算を回路で表現するために、昔の人は足し算の原理を利用することを発想しました。 8 - 6 は当たり前ですが 2 となりますね。これを 8 + (-6)で計算すると考え、引く方の-6 を何らか表現できれば良いということになります。

ここで補数という考え方を導入します。補数とはある数の桁が１つ増える為に必要な数のことです。6 の場合、補数は 4 です。6 + 4 = 10 のように桁が増える相方の数をイメージしてください。5 の補数は 5、3 の補数は 7 です。唐突ですが、引く方の 6 の補数 = 4 と 8 を足すと 12 となります。そして 12 の 10 の位を無視し、1 の位だけを注目すれば確かに、2 であるため、8 - 6 = 2 と同じ結果になりますね。このように補数を利用すれば、足し算の要領で引き算を実現することができます。

補数の足し算を利用するとなぜ引き算の結果が得られるのかは、不思議なようで当たり前でもあります。以下の式変形を見てください。
8 - 6 = 8 + (-6) = 8 + (10 - 6) - 10 = 8 + 4 - 10 = 2
確かに、補数を使って引き算を求めることができますね。

コンピュータの引き算は、実はこのような原理で動いています。
2 進数でも同じで引く方の数の補数さえ分かれば、足し算の原理を利用し、最上位を無視して引き算を実現することができます。
2 進数における補数は、実は以下のように機械的に求めることができます。

1. 全ビットを反転させる（1 と 0 を反転させる）
2. 1 を加算する

例えば 0101(10 進数における 5)の場合、全ビット反転で 1010、ここに 1 を加算して 1011(10 進数における 11)となります。
0101 + 1011 を計算すると、確かに桁が増えて 10000(10 進数における 16)となります。

改めて、8 - 6 を 2 進数で考えてみましょう。2 進数で表記すると、1000 - 110 となります。110 の補数は全ビット反転で 001、ここに 1 を足して 010(10 進数における 2)となります。
そして、1000 に 010 を足すと 1010、最上位を無視して 10(10 進数における 2)となりました。確かに正しい計算結果が得られていますね。

このようにコンピュータの引き算も、補数という概念と足し算の原理を組み合わせることで実現することができます。

掛け算と割り算

掛け算と割り算は極端な話、足し算と引き算をひたすら繰り返せば実現することができてしまいます。とはいえ、2 の倍数分の変化がある場合はシフト演算を使って簡単に表現することもできます。例えば、0110(10 進数における 6)を 2 倍するには、左に 1 桁ずらして右端に 0 を埋めます。そうすると 1100(10 進数における 12)となります。
これは、位置に応じて 2 進数の位の大きさが 2 の倍数で対応しているからですね。2 の 2 乗 = 4 倍したい場合は左に 2 つ分シフト演算することで求めることができます。

おわりに

勉強会第 4 回の内容として、bit 演算をテーマに学びました。

物理的な回路の原理は電圧の on, off の流れのパターンを作り出すことができます。これに 2 進法の数字を対応させ、位の概念を乗せることで計算処理を作ることができます。2 進数を基に全加算器を利用して足し算を実現し、補数を利用して引き算を実現できます。掛け算割り算は、足し算引き算の繰り返しで計算可能ですが、シフト演算を使うと簡単に 2 の倍数分の乗除を実現できたりします。

今回のテーマを通して、コンピュータはどのように計算を可能にしているのか？のイメージが持てるようになったかと思います。普段私たちが当たり前のように利用しているコンピュータの裏側を少しは覗けたのではないでしょうか？

次回の勉強会は連想配列についてです。