最近QBVHというデータ構造を実装しています。QBVHは4分木のようなデータ構造なのですが、メモリアクセス最適化の観点からノードのサイズを128Byteに抑えることを行います。ノードには座標値など既に多くのデータが入っているため、128Byteという制限ではメタ情報などを追加することが困難になっています。そこで1つの変数を数bitごとに切り分けて複数のデータを突っ込むということを行います。これは パッキング と言われるものですが、解説している記事があまりないようなので書いてみました。

エンコード

ここでは1つのint(32bit)にbool, 数値, 数値の3つのデータを書き込むことをやってみます。boolは先頭1bitで表現し、数値は残り4bitと残り27bitで表現することにします。

これはAND, OR, 左シフト, 右シフトなどのビット演算子を使うことで次のように行なえます。

bool v0 = true; // 先頭1bitに書き込むデータ
int v1 = 4; // 4bitに書き込むデータ
int v2 = 128; // 27bitに書き込むデータ

int enc = 0;
// 先頭1bitにデータを書き込む
enc |= (v0 << 31);

// 残り4bitにデータを書き込む
enc |= ((v1 & 0xf) << 27);

// 残り27bitにデータを書き込む
enc |= (v2 & 0x07ffffff);

以下では一つずつこの処理を解説していきます。

先頭1bitにデータを書き込む

まずはこの部分です。

// 先頭1bitにデータを書き込む
enc |= (v0 << 31);

これはまずv0のデータを31bit分だけ左シフトし、さらにencとOR演算を取るという処理です。v0はboolなので0か1のデータが入りますが、これを31bit左シフトすることで先頭ビットだけが0または1のビット列が作られます。

これをさらにencとOR演算を取ることで、encの先頭1bitだけにデータを書き込むことができます。

残り4bitにデータを書き込む

続いてこの部分です。

// 残り4bitにデータを書き込む
enc |= ((v1 & 0xf) << 27);

まずv1と0xfのAND演算を取ることでデータを4bitで表せるデータの範囲(0 - 15)までに抑えます。ここで0xfは2進数で表すと0b1111です。これとのAND演算を取ることで4bitの範囲にデータが抑えられます。

続いてデータを27bit左シフトします。こうすることで先頭2bit目 - 5bit目までだけに数値が入ったビット列が出来ます。後はこれをencとOR演算を取ることでencの先頭2bit目 - 5bit目までにデータを書き込めます。

残り27bitにデータを書き込む

最後にこの部分です。

// 残り27bitにデータを書き込む
enc |= (v2 & 0x07ffffff);

まず0x07ffffffとのAND演算を取ることでデータを27bitの範囲に抑えます。ここで0x07ffffffは2進数で表すと0b0000011111111...のように先頭6bit目以降が全て1となるような数字であることに注意してください。後はこれをencとOR演算を取ることでencの先頭6bit目以降にデータを書き込みます。

デコード

書き込んだデータを取り出すことをやってみます。逆の処理を行うだけです。

// 先頭1bitのデータを抜き出す
int dec0 = (enc & 0x80000000) >> 31;
std::cout << dec0 << std::endl;

// 4bitに書き込んだデータを抜き出す
int dec1 = (enc & 0x78000000) >> 27;
std::cout << dec1 << std::endl;

// 27bitに書き込んだデータを抜き出す
int dec2 = (enc & 0x07ffffff);
std::cout << dec2 << std::endl;

0x80000000は先頭1bitのみが1となるような数字です。同様に0x78000000は先頭2bit目 - 5bit目までが1となっているような数字です。これらの数字とAND演算を取ることでビット列を抜き出し、それを右シフトすることで元の数値に戻します。こういったプログラムを書く上では数字を2進数で表すとどのようなビット列になるのかを常に意識するのが大事ですね。

参考文献

• ビット演算まとめ