ビット演算

作成日時：2022/02/21(月) 07:00:30
更新日時：2022/02/23(水) 09:49:22

ビット演算 vs. 論理演算

AND(かつ)やOR(または)といった論理演算はよく知られていると思うので、ビット演算と比較しながら解説していきます。

	演算の行い方	演算の結果
ビット演算 (bitwise operation)	数字をビット列(すなわち二進数)に変換し、ビット(二進数の桁)毎に演算を行う	二進数
論理演算 (logical operation)	数字を真(true)(0でない場合)と偽(false)(0の場合)の二通りに変換し、二つの真偽値に対して演算を行う	trueかfalse (1か0)

true=1、false=0とすると、n bitのビット演算はn個独立の論理演算とみなせ、論理演算は1 bitのビット演算とみなせます。

bitwise vs logical

記号

SunScriptではビット演算と論理演算を行う時は次の記号を使います。

	ビット演算	論理演算
NOT	`~`x	`!`x
AND	a `&` b	a `&&` b
OR	a `\|` b	a `\|\|` b

※ これらの記号はC/C++/Java/JavaScriptなどと全く同じです。

計算方法

n bitはのビット演算はn個独立の論理演算(1 bitのビット演算)に過ぎないので、1 bitの場合の計算をできればn bitの場合も計算できます。1 bitのNOT、AND、OR演算は次の真理値表の通りに計算されます。

a	b	NOT b	a AND b	a OR b
0	0	1	0	0
1	0	1	0	1
0	1	0	0	1
1	1	0	1	1

よく観察すると、これらの演算は次の性質を持つことが分かります。

not-and-or

これらの性質の応用例して、コントローラのボタン入力を考えてみましょう。

応用例：ボタン入力

GCコンのボタンはStart、Y、X、B、A、L、R、Z、十字キー上、下、右、左の12個あります。ボタンは押されている(1)と押されていない(0)の2通りの状態しかないので、各ボタンの状態は1 bitで表せます。合計で12 bitになりますが、メモリに格納される最小単位は8 bitなので、サンシャインではボタンの入力は16 bitの整数で表されます。

サンシャインでは、各ボタンを表すbitは次のように定義されています。

var const PRESS_S  = 0x1000; // Start
var const PRESS_Y  = 0x0800;
var const PRESS_X  = 0x0400;
var const PRESS_B  = 0x0200;
var const PRESS_A  = 0x0100;
var const PRESS_L  = 0x0040;
var const PRESS_R  = 0x0020;
var const PRESS_Z  = 0x0010;
var const PRESS_DU = 0x0008; // 十字キー上
var const PRESS_DD = 0x0004; // 十字キー下
var const PRESS_DR = 0x0002; // 十字キー右
var const PRESS_DL = 0x0001; // 十字キー左

例えば、「B A L 左」が押されている時、ボタン入力の値は0x0341となり、その逆も同じです。

btn0

以下、ボタン入力の値をbtnとしていくつかの実例を考えましょう。

練習1：ボタンの組み合わせ

B、A、L、左が押されているとします。ボタン入力の値btnを上記の定数と~、&、|の組み合わせで表してみましょう。

解答例

異なるボタンの和集合を取るので、OR(|)を使います。よって、答えは次のようになります。

PRESS_B | PRESS_A | PRESS_L | PRESS_DL

btn1

練習1.5：ボタンの組み合わせ+論理式

「押されているボタンはB、A、L、左の4つであるかどうか」を表す論理式を上記の定数、btn、~、&、|、==の組み合わせで表してみましょう。

ヒント：a == bはaとbが等しいかどうかを表す論理式です。

解答例

押されているボタンがB、A、L、左の4つであることは、btnがPRESS_B | PRESS_A | PRESS_L | PRESS_DLと等しいであることと同値なので、答えは次のようになります。

btn == PRESS_B | PRESS_A | PRESS_L | PRESS_DL

練習2：他のボタンを無視

「Lと上が同時に押されているかどうか(その他のボタンの状態は問わない)」を表す論理式を上記の定数、btn、~、&、|、==、!=の組み合わせで表してみましょう。

解答例

「その他のボタンの状態は問わない」という条件が付いているので、練習1のようにbtn == PRESS_L | PRESS_DUにすると(この式は)単なる____条件になってしまいます。

____の答え (選択肢：十分、必要)

十分条件ですね。解説は割愛します。

~~解説が欲しい方はなおさんに聞いてください(X)~~

ここでANDの効果を思い出すと、AND 0は不要なbitを消すことができ、AND 1はbitを保持することができます。そのため、欲しいbitを1、捨てたいbitを0にしてANDを取ると、欲しいbitだけ残すことができます。このように個別のbitに対して操作を行うためのビット列(例えば下図のmask)をビットマスク(bitmask)と言います。

btn2-1

上図から分かるように、ANDする数字maskはPRESS_L | PRESS_DUとなります。また、ANDの結果はその他のボタンの状態を無視してLと上の二つのボタンだけ考慮した値となるので、この数字がPRESS_L | PRESS_DUと等しいことは「Lと上が同時に押されている」ことと同値となります。

よって、答えは次のようになります。

btn & (PRESS_L|PRESS_DU) == (PRESS_L|PRESS_DU)

練習3：部分無視

「AとBを除いて押されているボタンはLと上であるかどうか」を表す論理式を上記の定数、btn、~、&、|、==、!=の組み合わせで表してみましょう。

解答例

練習2のようにbitmaskを作ってANDすればいいですが、AとB以外のボタンを全部考慮する必要があるので、PRESS_S | PRESS_Y | ... | PRESS_DLのように全部ORで作ると非常に長くなってしまいます。(もちろんそれでも正解となります)

そこで、うまくNOTを使うと非常に短くできます。作りたいbitmaskを考えると、AとBを無視してその他のボタンを考慮するので、AとBのbitだけ0にして、その他のbitを1にする必要があります。そのため、bitmaskは次のようになります。

btn3-1

一部のbitが*となっていますが、それはそのbitはそもそも使われないので、0でも1でも結果は変わりません。そのため、我々の都合によく設定すればいいということになります。これをドントケア(Don't care)と呼ぶこともあります。

maskには1が多いので、NOTを取ると~maskはほぼ0になります。そこで、bitmaskを作る時は0から作るので、0が多ければ多いほど作るのが簡単になります。そのため、*は全部0を選びます。

btn3-2

したがって、~maskはPRESS_A | PRESS_Bとなります。両辺にNOTを取ると、mask = ~(PRESS_A | PRESS_B)となります。

btn3-3

そうすると、練習2と同じようにbtn & maskを計算すれば、「AとBを除いた押されているボタン」の値が求まり、この値が「Lと上」の値と等しいかどうかが答えとなります。

よって、答えは次のようになります。

btn & ~(PRESS_A | PRESS_B) == (PRESS_L | PRESS_DU)