ホーム < ゲームつくろー！ < Programming TIPs編
その17 ビット演算あれこれ
これだけ世の中進んでも、C言語の世界ではビット演算がどうしても欠かせない場面が色々と出てきます。ビット演算はパズルや魔法のようにほしい情報に変化していきます。あれやこれやをまとめてみました。
○ 立っているビットの数を数える
全ビットの中で立っているビットの数を数える時、1bitずつチェックしていくのはさすがに悲しくなります。これを計算する面白い方法があります。簡単な例で説明します。今8bitのビット列があるとしましょう：
id 7 6 5 4 3 2 1 0 bit列 1 1 1 0 0 1 0 0
これを「4」と数えられたら嬉しいわけです。このビット列をvalとしておきます。まずvalと01010101（0x55）との&を取ります。これをval1としておきましょう。またvalを1だけ右にシフトした値（上の場合は01111111）と01010101（0x55）との&も取ります。これはval2としておきます。そしてval1とval2を足し算します。その様子を表すと次のようになります：
id 7 6 5 4 3 2 1 0 val1 0 1 0 0 0 1 0 0 + val2 0 1 0 1 0 0 0 0 val1+val2 1 0 0 1 0 1 0 0
ビット同士の足し算は2進数での桁上がりを起こすので上のようになります。この演算で、隣同士の立っているビットの数が色分けされた部分にそれぞれ算出されて来ます。次に、この色分けされた同士が足し算できると良さそうですよね。その通りでして、00110011（0x33）と右に2シフトした値に対して同じ0x33を&取った値同士を足し算します：
id 7 6 5 4 3 2 1 0 val1 0 0 0 1 0 0 0 0 + val2 0 0 1 0 0 0 0 1 val1+val2 0 0 1 1 0 0 0 1
そうすると下の色分けした部分がそれぞれ「3」と「1」となって、確かに足し算されてきました。もうお分かりの通り、最後は00001111（0x0f）と右に4シフトした値と0x0fとで&を取り足し算すると答えが出てきます：
id 7 6 5 4 3 2 1 0 val1 0 0 0 0 0 0 0 1 + val2 0 0 0 0 0 0 1 1 val1+val2 0 0 0 0 0 1 0 0
どうでしょう、青い部分に確かに「4」が出てきましたよね。8bitの場合は正味3回の足し算で立っているビットの数が出てきます。同じ発想で16bitならば4回、32bitならば5回の足し算で答えが出ます。これはループを回すよりも恐ろしく速いですよね。
各bit単位での立っているビット数を数える関数はこんな感じになります：
各bit列での立っているビット数を算出 int count8bit(unsigned char v) {
unsigned count = (v & 0x55) + ((v >> 1) & 0x55);
count = (count & 0x33) + ((count >> 2) & 0x33);
return (count & 0x0f) + ((count >> 4) & 0x0f);
}
int count16bit(unsigned short v) {
unsigned short count = (v & 0x5555) + ((v >> 1) & 0x5555);
count = (count & 0x3333) + ((count >> 2) & 0x3333);
count = (count & 0x0f0f) + ((count >> 4) & 0x0f0f);
return (count & 0x00ff) + ((count >> 8) & 0x00ff);
}
int count32bit(unsigned v) {
unsigned count = (v & 0x55555555) + ((v >> 1) & 0x55555555);
count = (count & 0x33333333) + ((count >> 2) & 0x33333333);
count = (count & 0x0f0f0f0f) + ((count >> 4) & 0x0f0f0f0f);
count = (count & 0x00ff00ff) + ((count >> 8) & 0x00ff00ff);
return (count & 0x0000ffff) + ((count >> 16) & 0x0000ffff);
}
int count64bit(unsigned __int64 v) {
unsigned __int64 count = (v & 0x5555555555555555) + ((v >> 1) & 0x5555555555555555);
count = (count & 0x3333333333333333) + ((count >> 2) & 0x3333333333333333);
count = (count & 0x0f0f0f0f0f0f0f0f) + ((count >> 4) & 0x0f0f0f0f0f0f0f0f);
count = (count & 0x00ff00ff00ff00ff) + ((count >> 8) & 0x00ff00ff00ff00ff);
count = (count & 0x0000ffff0000ffff) + ((count >> 16) & 0x0000ffff0000ffff);
return (int)((count & 0x00000000ffffffff) + ((count >> 32) & 0x00000000ffffffff));
}
○ 最大有効ビット数（MSB：Most Significant Bit）
立っている一番最大ビットを取得する場面もままあります。これはMSBと呼ばれています。色々やり方はあると思いますが、先程立っているビット数を高速に取得できるようになったので、これを利用することにしましょう。
id 7 6 5 4 3 2 1 0 bit列 0 0 1 0 0 1 0 1
こんな感じのビット列があったとします。5bit目がMSBです。まず最初に元のbit列と右へ1つシフトしたビット列とのorを取ります：
id 7 6 5 4 3 2 1 0 val1 0 0 1 0 0 1 0 1 or val2 0 0 0 1 0 0 1 0 0 0 1 1 0 1 1 1
こうすると少なくとも最大bitとその右となりのbitが立ちます。続いて今度は今求めたbit列と右へ2シフトしたビット列とのorを取ります：
id 7 6 5 4 3 2 1 0 val1 0 0 1 1 0 1 1 1 or val2 0 0 0 0 1 1 0 1 0 0 1 1 1 1 1 1
もう見えたと思いますが、最後に今のbit列と右へ4シフトしたビット列とのorを取ります：
id 7 6 5 4 3 2 1 0 val1 0 0 1 1 1 1 1 1 or val2 0 0 0 0 1 1 1 1 0 0 1 1 1 1 1 1
これで最大列の右側が全部立ちました。後はこの立っているビットの数を数えるだけです。これは先のcount8bit関数に渡せば一発です。これと同じ方法を16、32、64bitの数字にも適用できます。
MSBを求める関数は例えばこうなります：
MSB bool MSB8bit(unsigned char v, int &out) {
if (v == 0) return false;
v |= (v >> 1);
v |= (v >> 2);
v |= (v >> 4);
out = count8bit(v) - 1;
}
bool MSB16bit(unsigned short v, int &out) {
if (v == 0) return false;
v |= (v >> 1);
v |= (v >> 2);
v |= (v >> 4);
v |= (v >> 8);
out = count16bit(v) - 1;
}
bool MSB32bit(unsigned v, int &out) {
if (v == 0) return false;
v |= (v >> 1);
v |= (v >> 2);
v |= (v >> 4);
v |= (v >> 8);
v |= (v >> 16);
out = count32bit(v) - 1;
}
bool MSB64bit(unsigned __int64 v, int &out) {
if (v == 0) return false;
v |= (v >> 1);
v |= (v >> 2);
v |= (v >> 4);
v |= (v >> 8);
v |= (v >> 16);
v |= (v >> 32);
out = count64bit(v) - 1;
}
○ 最小有効ビット数（LSB：Least Significant Bit）
MSBとは逆にビットの下から数えて初めて出現した1のビット数を算出するには、MSBと似た方法が使えます。すなわち、今度は左へ左へとシフトして立ったビットの数を数え上げれば良さそうです：
各bit列での立っているビット数を算出 bool LSB8bit(unsigned char v, int &out) {
if (v == 0) return false;
v |= (v << 1);
v |= (v << 2);
v |= (v << 4);
out = 8 - count8bit(v);
}
bool LSB16bit(unsigned short v, int &out) {
if (v == 0) return false;
v |= (v << 1);
v |= (v << 2);
v |= (v << 4);
v |= (v << 8);
out = 16 - count16bit(v);
}
bool LSB32bit(unsigned v, int &out) {
if (v == 0) return false;
v |= (v << 1);
v |= (v << 2);
v |= (v << 4);
v |= (v << 8);
v |= (v << 16);
out = 32 - count32bit(v);
}
int LSB64bit(unsigned __int64 v, int &out) {
if (v == 0) return false;
v |= (v << 1);
v |= (v << 2);
v |= (v << 4);
v |= (v << 8);
v |= (v << 16);
v |= (v << 32);
out = 64 - count64bit(v);
}
○ 整数Xを含む最小のべき乗数
べき乗テクスチャを作成するときなどは、任意の数Xを含む一番小さいべき乗数を求める必要があります。例えば57だったら64、119なら128という感じです。2のべき乗数はビット列のどこか１つだけが立っている数字です。そしてその右側のビット列を含めることができます。という事は任意の数XのMSBを求めれば良さそうに思います。しかし、例えばX=64の場合は64が最小べき乗数です。64のMSBは6です。でも65だと128すなわちMSBが7の整数が必要になります。65のMSBも6です。
具体的な数字で見てみると、
数値 最小べき乗数 数値-1 数値-1のMSB + 1 60 64 59 6 61 64 60 6 62 64 61 6 63 64 62 6 64 64 63 6 65 128 64 7 66 128 65 7
と元の数値から1を引いた数のMSBを+1した値が求めるべき乗数のようです。各bitでのべき乗数を求める関数はこちら：
各bit列での立っているビット数を算出 int calcSquare8bit(unsigned char v) {
if (v == 0) return 0;
return 1 << (MSB8bit(v - 1) + 1);
}
int calcSquare16bit(unsigned short v) {
if (v == 0) return 0;
return 1 << (MSB16bit(v - 1) + 1);
}
int calcSquare32bit(unsigned v) {
if (v == 0) return 0;
return 1 << (MSB32bit(v - 1) + 1);
}
int calcSquare64bit(unsigned __int64 v) {
if (v == 0) return 0;
return 1 << (MSB64bit(v - 1) + 1);
}
他にもビット演算は色々とありますが、気が付いた時に更新します〜(^-^)/