Programming Tips: ビット演算
導入
論理演算
0 と 1 のいずれかの値を取る変数、すなわち１ビットの変数 \(x, y\) に対し、 演算 \(\lnot x\), \(x \land y\), \(x \lor y\), \(x \oplus y\) を 否定 (not) 、論理積 (and) 、論理和 (or) 、排他的論理和 (xor) と呼び、 以下のように定義される。
否定 (not)
| \(x\) | \(\lnot x\) |
|---|---|
| 0 | 1 |
| 1 | 0 |
論理積 (and)
| \(x\) | \(y\) | \(x \land y\) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
論理和 (or)
| \(x\) | \(y\) | \(x \lor y\) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
排他的論理和 (exclusive or - xor)
| \(x\) | \(y\) | \(x \oplus y\) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
ビット演算 (Bitwise Operators)
- n ビットの変数 x, y に対し、各ビット毎 (bit-wise) に 上記の論理演算を適用すること。
- C 言語および多くの言語では、それぞれ ~, &, |, ^ 演算子が該当する。
以下に例を示す（変数はわかりやすく 8 ビットとしよう）。
bitwise not
| 二進数 | 16進数 | 10進数 | |
|---|---|---|---|
| x | 00001111 | 0x0f | 15 |
| ~x | 11110000 | 0xf0 | 240 |
bitwise and
| 二進数 | 16進数 | 10進数 | |
|---|---|---|---|
| x | 01010101 | 0x55 | 85 |
| y | 00001111 | 0x0f | 15 |
| x & y | 00000101 | 0x05 | 5 |
この演算では、x and 0 = 0, x and 1 = x になることから、 ビット列中の特定のビットだけ注目したい時に役立つ。
この例では、00001111 と and を取っているので、 x の下位４ビットである 0101 がそのまま抽出され 上位４ビットはすべて 0 になる。このような操作をマスクとも呼ぶ。
bitwise or
| 二進数 | 16進数 | 10進数 | |
|---|---|---|---|
| x | 01010101 | 0x55 | 85 |
| y | 00001111 | 0x07 | 7 |
| x| y | 01011111 | 0x5f | 95 |
この演算では、x or 0 = x, x or 1 = 1 になることから、 特定のビットを 1 にし、その他のビットは変化させない、 という処理を行うことができる。
この例では、上位４ビットは 0101 のまま変化せず、 下位４ビットを 1111 に変化させた。
bitwise xor
| 二進数 | 16進数 | 10進数 | |
|---|---|---|---|
| x | 01010101 | 0x55 | 85 |
| y | 00001111 | 0x07 | 7 |
| x ^ y | 01011010 | 0x5a | 90 |
この演算では、y で指定したビットパターンに基づいて、 x のビットを反転させることができる。 y = 00001111 なので、 x の上位４ビットはそのまま変化させず、 下位４ビットだけ 0と1 を反転させる、という操作になる。
基本編
これらを組み合わせて、１つの変数に複数のフラグをまとめることもできる。 例として、RPG を作ることを考えよう。 キャラクターの状態異常を、
enum BadStatus {
PARALYSIS = 1,
POISON = 2,
SLEEP = 4,
STUN = 8,
}
と定義する。例えば、スタンと麻痺を同時に受けているときは、 それぞれの数値を足し合わせた 9 になる。さて、変数 status に対して
if ( status & BadStatus::PARALYSIS ) {
// 麻痺している //
}
if ( status & BadStatus::POISON ) {
// 毒を受けている //
}
...
とすることで、各状態異常の判定ができる。
同様に、敵の攻撃を受けて毒の状態異常が付与された時は、
status = status | BadStatus::POISON;
と書くことができる。この時、 変数は各状態異常を示す定数の和だからと言って、間違っても
status = status + BadStatus::POISON;
と書いてはいけない。これでは、 すでに毒を受けている状態で、さらに毒を受けると （数値が 4 になるから）なぜか毒が解除されて眠ってしまう。
if ( status & BadStatus.POISON == 0 ) {
status = status + BadStatus::POISON;
}
と判定してもよいが、元の値が 0 でも 1 でも目的のビットだけ 1 （他はそのまま） にできる or を使うのが単純だし、コードの意図も分かりやすい。
同様に、解毒魔法を使ったときは、
status = status & (~ BadStatus::POISON);
でよい。この場合もうっかり引き算してしまうと、 毒を受けていないキャラクタに解毒魔法を使うと逆に毒を受けてしまう （最悪、繰り下がって、眠りとスタンも受ける）というバグが発生する。
おまけ
先の例では、各状態に１ビットずつ使ったが、 特定のビットは数ビットで１要素としてもよい。 例えば下位２ビットに戦闘から逃げるのに失敗した回数、 残りのビットが１ビット１フラグ、 等である。 この場合は、逃げた回数の増加の際には
flag = (flag + 1) & 0x03 | (flag & 0xfc)
のようにきちんとマスクをしないと、余計なビットに繰り上がるバグが発生する。 実際、ファミコン時代の某有名なゲームでこの致命的なミスがある。
そのゲームでは、
- (C) 複数の効果の中からランダムな効果が出るギャンブル魔法があり、そのうちの一つに、その戦闘中味方の攻撃にすべてクリティカルになる効果がある
- (D) 敵の特殊能力で、敵味方ともに魔法が使えなくなるものがある
- (T) 戦闘開始時まで時間を戻すアイテムがある。 一度使うと宿にとまるまで使えない（だったと思う）。 少なくとも１戦闘中は１回まで。
というフラグと、戦闘から逃げた回数 (E) を、 １つの変数に管理していたと思われる。 裏技サイトなどを参考に推測すると、以下のようなビット列と思われる
| bit | 7 | 6 | 5 | 4 | 3 | 2 | 1…0 |
|---|---|---|---|---|---|---|---|
| 意味 | (D) | ??? | ??? | ??? | (C) | (T) | (E) |
（??? の部分は不明）
したがって、戦闘から逃げるのに８回失敗すると、 味方の攻撃がすべてクリティカルヒットになるという裏技がある （初期出荷版に限る）。
実際には４回目には必ず逃げられる仕様と思われるが、 ボス戦では逃げられないので、このバグにより、ラスボスをボコれる。
ちなみに、裏技サイトによると、 先に (T) のアイテムを使っておけば、８回ではなく４回で済むし、 １２８回逃げるのに失敗すると、突然魔法が使えなくなる。（らしい）。
応用編
剰余
- 特定の条件において、ビット演算を、剰余の代わりに使うことができる
- 具体的には、除数が 2 のべき乗になっているときに限るが、 一般に通常の除算命令より高速になることが多い
考えやすくするため、まず 10 進数の場合
-
例１） 1234 を 10 で割った余りは 4 である。 これは 1234 の下位１桁を取り出したことに等しい。
-
例２） 1234 を 100 つまり、\(10^2\) で割った余りは 34 である。 これは 1234 の下位２桁を取り出したことに等しい。
- 同様にして x を \(10^n\) で割った余りは、 x の下位 n 桁を取り出すことになる。
- なお、この方法が使えるのは、除数が \(10^n\) の場合に限られる。
2 進数の場合
この考え方は、2 進数の場合にも適用できる。
- 例１） 00100011 を 10 で割った余りは 1 である。10 進数で書けば 35 ÷ 2 = 17 余り 1
- 例２） 00100011 を 100 で割った余りは 11 である。同 35 ÷ 4 = 8 余り 3
- 例３） 00100011 を 1000 で割った余りは 011 である。同 35 ÷ 8 = 4 余り 3
さて、導入で説明した通り 抽出したいビットを 1 それ以外を 0 にしたビットパターンと bitwise and 特定のビットだけ取り出せるのであった。
したがって、上の各例は
- 例１） 00100011 & 00000001 = 00000001
- 例２） 00100011 & 00000011 = 00000011
- 例３） 00100011 & 00000111 = 00000011
のようにあらわすことができる。
すなわち、除数が \(d = 2 ^ n\) の場合に限り、 x を d で割った余りを求める公式は、
x & (d - 1)
である。例えば x を 16 で割った余りは
x & 15
となる（除数は 16 だが & を使うときは 15 になるので注意）。
切り捨て
切り捨ては、剰余とは逆に、 下位ビットを 0 で埋めてしまえばよい。
- 例） 1234 を 100 の倍数に切り捨てると、 下２桁を 0 にして 1200 である。
- 例） 00100011 を 1000 の倍数に切り捨てると、 下３ビットを 0 にして 00100000 である。 10進数 で書けば、35 を 8 の倍数に切り捨てると 32 ということである。
これを実現するには、上位ビットを 1、下位３ビットを 0 とした 11111000 と bitwise and をとり、 00100011 & 11111000 = 00100000 (35 & 247 = 32) となる
なお、11111000 というパターンを作るには、bitwise not を使えば 11111000 = ~ 00000111 である。
したがって、\(d = 2 ^n\) の場合に限り、 ある数 x を d の倍数に切り捨てる公式は
x & ~(d - 1)
である。例えば 16 の倍数に切り捨てるなら
x & ~15
となる。
切り上げ
切り上げは、適切な定数を加えてから切り捨てればよい。
- 例） 1234 を 10 の倍数に切り上げるには、 1234 + 9 = 1243 としてから切り捨てれば 1240 が得られる。
- 例） 1234 を 100 の倍数に切り上げるには、 1234 + 99 = 1333 としてから切り捨て 1300 が得られる。
- 例） 1200 を 100 の倍数（元から 100 の倍数) に切り上げると 1200 + 99 = 1299 となって、これを切り捨てると 1200 となる。
これは 2 進数でも同様で、\(d = 2^n\) の場合に限り、 ある数 x を d の倍数に切り上げる公式は、
(x + d - 1) & ~(d - 1)
となる。例えば 16 の倍数に切り上げるなら
(x + 15) & ~15
である。
tags: