(AS3)ビット演算を倒す

ビット演算（ビットえんざん）とは、
ひとつあるいはふたつのビットパターンまたは二進数を個々のビットの列として操作することである。

CPUからすればビット演算は簡単な論理回路で実現できるが、
四則演算、特に乗除算は複雑な論理回路を必要とするため、
多くのコンピュータでは、ビット演算は加減算より若干速く、乗除算よりずっと高速である。

Wikipedia(ビット演算) より

AS3 でもビット演算で高速化するなどという Tips をよく見かけたりします。
早いのはわかったけど「なぜそうなるのか。」「実際どんな場面で使ったりするものなのか」などはなかなか書いてなかったり。
なので今回は例を含めつつ、説明していこうと思います。

「得意な人はより得意に、そうでない人はそれなりに」を目指します。

---

二進法

苦手な人はいきなりブラウザバックしたくなる話だと思いますが少し我慢してください。
二進法を理解しないとさすがにこの先の話はきついと思うのでさくっと(大体あってる程度で)説明します。

日常用いられている、十倍ごとに位をとる数の表記法は十進法と呼ばれています。
零から九までの十通りの数値については、
それぞれを表す 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 というような専用の文字（数字）が用意されています。
そして 9 より一だけ大きい十を一文字で表記せず、1 と 0 の二文字を組み合わせて 10 と桁を上げて表記します。

それに対して今回説明する 二進法 は 0, 1 のみで表します。
1より一だけ大きい数を「2」と一文字で表記せず、1 と 0 を二文字あわせて 10 と桁を上げて表記します。
二進法での 10 は 「二」であって、「十」ではありませんので注意してください。

それぞれ N進法で表された数字のことを N進数、二進法で表された数字は 二進数 といいます。

もう一度、十進法に戻ります。
10 の意味は、1 の位 が 0 で 10の位が 1 である数字という意味ですね。
さらに 247 の意味は 1の位が 7 で 10の位が 4 で 100の位が 2 の数字という意味です。

二進法も同じように考えます。
10(2) の意味は、1 の位が 0 で 2 の位が 1 である数字という意味です。
さらに、1101 の意味は、 1の位が 1 で 2の位が 0 で 4の位が1 で 8 の位が 1 の数字という意味になります。

一般的な人に二進数をそのまま理解するのは難しいと思います。
なので普段使っている十進数を二進数に変換する(または逆に二進数を十進数に)方法だけは理解しておきましょう。
今後 二進数で表されたものには 101110(2) という風に(2)をつけて表記します。

例えば、46を二進数で表記するには、46を ずっと2で割って答えが0になるまで続けます。

46 / 2 = 23 … あまり0
23 / 2 = 11 … あまり1

11 / 2 = 5 … あまり1
5 / 2 = 2 … あまり1
2 / 2 = 1 … あまり0
1 / 2 = 0 … あまり1

このあまりを逆にして横に並べた 101110(2) が 二進数の 46 になります。

逆に 101110(2) を十進数に直すにはそれぞれの桁毎にそれぞれの桁の低い順に 2^0, 2^1, 2^2, 2^3, 2^4 … をかけてその総和で求めることができます。
ちなみに 2^3 は 2の3乗 と読みます。(後に出てくるビット演算子とは違いますので注意)

0*(2^0) + 1*(2^1) + 1*(2^2) + 1*(2^3) + 0*(2^4) + 1*(2^5) =
0*(1) + 1*(2) + 1*(4) + 1*(8) + 0*(16) + 1*(32) =
2 + 4 + 8 + 32 = 46

毎度計算するのが面倒な人は Windows の場合であれば、デフォルトで入っている電卓を使うと便利です。
表示を関数計算機に変えて 十進数で入力した後に、 上のラジオボタンで 2進 を選ぶと 二進数 にしてくれます。

これから ビット という言葉が多く出てきますが、
ビットとはこの二進法で表された数字の桁のことを言います。
1011(2) であれば 4ビット、さらに 4ビット目、 2ビット目、 1ビット目が立っていると考えます。

---

変数の値

var hoge: int = 0;
var moja: uint = 0;

と書いたときにそれぞれの値はどうやって保持されているのかという話をざっくりとしていきます。
これがビット演算と何が関係があるの？思うかも知れませんが非常に深く関係してきます。
しかし、事細かに説明をしていると日が暮れてしまうので、関係のある部分だけ説明していきます。

int や uint が作られた時、
32ビット分のデータが入る領域が変数ひとつに対して一個作られます。(本当はもっと細かく色々と作られると思うが割愛します。)
32ビットは 11111111111111111111111111111111(2) のように 1 が32個並んだ数まで値として持つことができます。
十進数で表すならば 0 ～ 4294967295 までを表すことができるということです。

4294967295 の値に + 1 すると
11111111111111111111111111111111(2) + 1(2) で
100000000000000000000000000000000(2) になります。
でも32ビットまでしか値を持つことができないので 33ビット目からは無視されます。
つまり 値が 0 になります。
この 0 ～ 4294967295 を繰り返すことを覚えておいてください。

---

二進数の負(マケじゃないよ)

二進数を表すときに、「負の数」はどうやって表すのかという話です。
uint は 負の数が存在しないので int として考えます。
負の数を表記するときは十進数と同じく普通に “符号” をつけて -10110(2) のように書いてよいですが、

それをどのようにして値を持っているのかを考えてみましょう。

int の 最大値(max)は、 2147483647、二進数で表すと 1111111111111111111111111111111(2) です。
int の 最小値(min)は、-2147483648、二進数で表すと -10000000000000000000000000000000(2) です。

int は符号付き32ビット整数です。
なのになぜ max が31ビットなのでしょうか。
それに比べ min は32ビットです。しかし32ビット全てのビットは立っていません。
このまま色々と検証してもよいのですが、32ビットで見るとさすがに桁が多すぎるので、仮に4ビット符号付き整数を過程して考えてみます。
4ビット整数は 0(2) ～ 1111(2)、0 ～ 15 までの16種類です。
4ビット符号付き整数の場合は、先ほどの int と同じように考えると -1000(2) ～ 111(2)、-8 ～ 7 までの16種類になるはずです。

初めは、最後の1ビット(32ビット目)が符号(1 が - で 0 が + )を表すものだと思っていました。
しかし、111(2) に 1 を足した時に1000 になるのであれば、答えは -0 にならなければ計算が合いません。
もし、1000(2) が -0 だとするならば、1111(2) は -7 であるはずです。
1000(2) が -1 だと考えるなら、 1111(2) が -8 で 正しいような気がします。
しかし、
int の max に 1 を足し時の値は min になっていました。
111(2) が max で 1111(2) が min だとしたら、そんなにめんどくさい処理にするでしょうか？
つまり、この答えは正解とは言い切れません。

では、111(2) が max で、1を足したら min になり、min が 1000(2) であるためにはどう考えるのが正解なのでしょうか。

こう考えれば全てのつじつまが合いそうな気がします。

7 0111
-8 1000
-7 1001
-6 1010
-5 1011
-4 1100
-3 1101
-2 1110
-1 1111
0 0000

4ビット目、つまり最後のビットだけがマイナス値(-8)になっていると考えると全ての計算が合いそうです。
符号付きの整数を考えるとき、持っている値の計算は今の例で表したように計算が特殊になりますので注意してください。

後から調べてわかったのですが、
負の表し方には色々と存在するようです。
知りたい方はいろいろと調べて見ると面白いと思います。
符号付数値表現 - Wikipedia
http://ja.wikipedia.org/wiki/%E7%AC%A6%E5%8F%B7%E4%BB%98%E6%95%B0%E5%80%A4%E8%A1%A8%E7%8F%BE

---

ビット単位シフト演算(ビットシフト)

今までは二進数のお話ばかりでしたが、やっとここからビット演算らしくなります。
ビット演算の全てが終わったら、どんな場面で使われるのか、例を挙げていこうと思います。

ビットシフト演算には3種類の演算があります。
x << y, x >> y, x >>> y
の3種類です。
<< を ビット単位の左シフト演算子。
>> を ビット単位の右シフト演算子。
>>> を ビット単位の符号なし右シフトと読みます。
x の数字を y だけビットシフトさせます。
ビットシフトとは名の通り、ビットをずらすことです。

ビットをずらすとはどんなことがおきることなのか。
なぜそうなるのかも含め説明していきます。
先ほどの説明でもあった通り、ビットとは 二進数の桁の事 です。
なので、二進数に変換して考えます。

左シフト(<<)

例えば、 11 << 3 を考えてみます。
11 を二進数で表すと、1011(2) です。
この 1011(2) の桁を三つ左にずらしてみます。
すると 1011000(2) という数に変わりました。
これを十進数に戻すと、88 になります。
これが左シフトです。

左シフトにはどんな特徴があるかというと、
元の数に 2 をかけていくことができるということ。
x << y を x * 2^y と考えることができます。

ただし、注意があります。
先ほど説明したとおり、
int の 正の値を超え、32ビット目が立つと負の値になりますので注意が必要です。
先ほどの 88 (1011000(2)) をさらに左シフトさせて、その挙動を見てみましょう。

176 10110000(2)
352 101100000(2)
704 1011000000(2)
1408 10110000000(2)
2816 101100000000(2)
…(中略)
369098752 10110000000000000000000000000(2)
738197504 101100000000000000000000000000(2)
1476395008 1011000000000000000000000000000(2)
-1342177280 10110000000000000000000000000000(2)
1610612736 01100000000000000000000000000000(2)
-1073741824 11000000000000000000000000000000(2)
-2147483648 10000000000000000000000000000000(2)
0 0(2)

といったように変化していきます。
左端(32ビット目) を超えると、その数字は消え、最終的には0になります。
この点を注意しましょう。

右シフト (>>)

左シフトを見た人はなんとなく答えを予想しているのでは無いでしょうか。
ではまた例を挙げつつ見ていきます。

例えば、 88 >> 3 を考えてみます。
88 を二進数で表すと、1011000(2) です。
この 1011000(2) の桁を三つ右にずらしてみます。
すると 1011(2) という数に変わりました。
これを十進数に戻すと、11 になります。
これが右シフトです。

右シフトにはどんな特徴があるかというと、
元の数を 2 で割っていくことができるということです。
x >> y を x / (2^y) と考えることができます。

ただし注意が必要です。

まずは、0になるまでビットシフトさせてみましょう。

44 101100(2)
22 10110(2)
11 1011(2)
5 101(2)
2 10(2)
1 1(2)
0 0(2)

のようになります。

88 >> 4 をみてみましょう。結果の4行目です。
上の式のように計算すると、
88 / (2^4) = 88 / 16 = 5.5 となってしまいます。
実際に答えとしては 88 >> 4 で出力される値は 5 です。
ならば、AS3 風に書くと Math.floor(x / Math.pow(2, y)) が正解でしょうか？

では今度は負の値を右シフトさせたときのことを考えて見ます。

-11 を右シフトさせていきます。
いちいち計算するのが面倒なので計算させる、プログラムを AS3 で書いてみました。

var i: int = -11;
do { trace(i, i.toString(2) + "(2)"); i = i >> 1; }
while (i != 0)

これで出力してみます。

-11 -1011(2)
-6 -110(2)
-3 -11(2)
-2 -10(2)
-1 -1(2)
-1 -1(2)
-1 -1(2)
…(略)

と表示されました。
ビットの表示が妙な動きになっていることがわかると思います。
さらに、最後、-1 ずっと続いています。
これはなぜでしょうか。

ココで二進数の負の話が関係してきます。
最終ビット目だけが マイナス値 だという話をしました。
-1 の値を思い出してください、
4ビットの符号付整数の -1 の値は 1111(2) でした。
つまり 32ビットの符号付整数でも -1 の値は 11111111111111111111111111111111(2) になっていると考えられます。
通常、この値は 32ビット目が マイナス値でなければ、4294967295 です。
この値、は uint の max と同じです。
つまり、一度 int の値を uint に直せば、正しい値が表示できるというわけです。
その表示ができるように、プログラムを修正してもう一度実行してみます。

do { trace(i, i.toString(2) + "(2)", uint(i).toString(2) + "(2)"); i = i >> 1; }
while (i != 0 && !(i == i >> 1))
trace(i, i.toString(2) + "(2)", uint(i).toString(2) + "(2)");

このように修正をして実行しました。

-11 -1011(2) 11111111111111111111111111110101(2)
-6 -110(2) 11111111111111111111111111111010(2)
-3 -11(2) 11111111111111111111111111111101(2)
-2 -10(2) 11111111111111111111111111111110(2)
-1 -1(2) 11111111111111111111111111111111(2)

と表示されました。
なぜ 変な挙動をしていたのか、なぜ -1 がずっと続いていたのか。
こう見るとわかりやすいですね。

まとめます。
「右シフトは 右にビットを一桁ずらして、左端の数字で 32 ビットを埋めていくこと。」

プラス値の場合は左端は 0 ビットで埋まります。
特徴は先ほど書いた、Math.floor(x / Math.pow(2, y)) の式で大体あっているようです。

符号なし右シフト(>>>)

一部の挙動を除いて、右シフトと同じです。
その一部の挙動とは、
「右シフトと同じように 右にビットを一桁ずらして、左端は 0 で埋めていきます。」

なので int.MIN_VALUE を符号なし右シフトしていくと結果は以下のようになります。

-2147483648 -10000000000000000000000000000000(2) 10000000000000000000000000000000(2)
1073741824 1000000000000000000000000000000(2) 1000000000000000000000000000000(2)
536870912 100000000000000000000000000000(2) 100000000000000000000000000000(2)
268435456 10000000000000000000000000000(2) 10000000000000000000000000000(2)
…(略)
4 100(2) 100(2)
2 10(2) 10(2)
1 1(2) 1(2)
0 0(2) 0(2)

左端は 0 で埋められるので最終的には 0 に収束します。
符号なし右シフトに関しては、右シフトとほぼ同じなので説明は終了です。

---

ビット単位論理演算と否定

ビット単位論理演算は、ビット単位で論理演算を行います。
ビット単位論理演算には以下の種類があります。
x & y, x | y, x ^ y, ~ y
& は ビット単位の論理積(AND)演算子。
| は ビット単位の論理和(OR)演算子。
^ は ビット単位の排他的論理和(XOR)演算子。
~ は ビット単位の否定(NOT)演算子 と読みます。

さて、そもそも論理演算とはどんな演算なのでしょうか。

論理演算とは

ブール演算と大体同じです。
1(true, 真) か 0(false, 偽) の 2通りの入力値に対して一つの値を出力する演算です。
簡単に言うと 入力された 1 と 0 に対して 1 と 0 を返す演算を行います。
集合と同じように考えればいいと思います。

ビット単位の論理積(AND)演算子 (&)

result = x & y

上のように書き、見た目通りの効果を表します。
ビット単位で x かつ y の関係を表します。

さて、例として 26 & 11 を見てみます。
それぞれを二進数で表します。
11010(2) と 1011(2) で x かつ y の関係を見ていきます。
それぞれのビットが立っているところだけが答えとして出力されます。
つまり、11010(2) と 1011(2) でそれぞれのビットの立っている桁だけが答えとして出力されますので
01010(2) が答えとして出力されます。10 が答えです。

ビット単位の論理和(OR)演算子 (|)

result = x | y

上のように書き、見た目通りの効果を表します。
ビット単位で x または y の関係を表します。

さて、例として 18 | 11 を見てみます。
それぞれを二進数で表します。
10010(2) と 1011(2) で x または y の関係を見ていきます。
それぞれのビットで立っている桁があれば 1 を出力します。
つまり、10010(2) と 1011(2) でどちらかのビットの立っている桁が1として出力されますので
11011(2) が答えとして出力されます。27 が答えです。

ビット単位の排他的論理和(XOR)演算 (^)

result = x ^ y

上のように書きます。
これは見た目通りとはいきません。
入力値の同じ部分以外(入力値が異なる場合)に1を出力します。

さて、例として 26 ^ 11 を見てみます。
それぞれを二進数で表します。
11010(2) と 1011(2) で x と y の関係を見ていきます。
それぞれのビットが変わっているところだけが1として出力されます。
つまり、11010(2) と 1011(2) でそれぞれのビットが変わっている桁だけが答えとして出力されますので
10001(2) が答えとして出力されます。17 が答えです。

ビット単位の否定(NOT)演算子 (~)

result = ~ y

上のように書きます。
これは他の演算子とは違い、使いどころが難しい演算子です。
これは入力値を含まない全てを返します。

さて、例えば ~ 26 を見てみます。
それぞれを二進数で表します。
11010(2) の値以外の全てですので、11111111111111111111111111111111(2) と比べて 11010(2) の含まない値を返します。
11111111111111111111111111100101(2) として答えが返ってきます。-27 が答えです。

さて、これでビット演算自体の説明は終わりです。
このビット演算を使ってどんなことができるのかをこれから説明していこうと思います。

---

実例

RGB

コンピュータ上で色を表す数値です。
0xFFFFFF ～ 0×000000 までの 16777215色を表すことができます。
ビット演算がよくつかわれる場所でもあります。

RGB からそれぞれの数値だけを取り出す。

var color: uint = 0xFF1234;
trace(color); // 16716340
trace(color >> 16 & 0xFF); // 255
trace(color >>  8 & 0xFF); // 18
trace(color >>  0 & 0xFF); // 52

それぞれの数値から RGBを求める。

var r: uint = 0xFF;
var g: uint = 0x12;
var b: uint = 0x34;
trace(r << 16 | g << 8 | b); // 16716340

よく見るのはこんな感じですね。

ゲームでよくつかわれるビット演算。

ターンチェンジ
オセロなどでよく使う手です。

var i: int = 1;
trace(i); // 1
trace(i = i ^ 3); // 2
trace(i = i ^ 3); // 1
trace(i = i ^ 3); // 2
trace(i = i ^ 3); // 1

移動フラグ
カヤックさんのInfinity tank battle(http://flash-games.wonderfl.net/tank/)などでも使われていると思います。

private function loop(e: Event): void
{
	/*
	if (action == (1 << 0)) target.x -= 2;
	if (action == (1 << 1)) target.y -= 2;
	if (action == (1 << 2)) target.x += 2;
	if (action == (1 << 3)) target.y += 2;
	*/
	if (action & (1 << 0)) target.x -= 2;
	if (action & (1 << 1)) target.y -= 2;
	if (action & (1 << 2)) target.x += 2;
	if (action & (1 << 3)) target.y += 2;
}

private function keyDown(e: KeyboardEvent): void
{
	var key: int = 0;
	switch (e.keyCode)
	{
		case 37: key = 1 << 0; break; // left
		case 38: key = 1 << 1; break; // up
		case 39: key = 1 << 2; break; // right
		case 40: key = 1 << 3; break; // down
	}
	action |= key;
}

private function keyUp(e: KeyboardEvent): void
{
	var key: int = 0;
	switch (e.keyCode)
	{
		case 37: key = 1 << 0; break; // left
		case 38: key = 1 << 1; break; // up
		case 39: key = 1 << 2; break; // right
		case 40: key = 1 << 3; break; // down
	}
	action &= -1 - key;
	// action &= ~ key; // こっちでも可
}

こんな書き方をして移動などのフラグを管理します。

簡易 3D 座標

x_, y_ の位置にいる、ボックスのそれぞれの頂点の座標を求めます。
var x_: int = 2, y_: int = 3;
for (var i:int = 0; i < 8; i++)
{
	trace(x_ + (i >> 0 & 1), y_ + (i >> 1 & 1), i >> 2);
}

とりあえずこんな感じでしょうか。
まだまだ、便利に使う方法があるはずです。
また、思いついたり教えてもらったりしたらまとめて紹介したいと思います。

追記
BeInteractive! さん(http://www.be-interactive.org/)のところで紹介してもらいました。
さらに、ここに載っていないテクニックも紹介してもらっています。
興味のある方はこちらへどうぞ。
BeInteractive! [ビット演算って面白いですよね] (http://www.be-interactive.org/index.php?itemid=519)