出力を入力へ

プログラミングに関する基本的な事を中心にまとめます

リングバッファの識別子にビットマスクを用いる

言語によらず、プログラムを書くときの実装技術の1つ。
特にメモリの制約がゆるく、リングサイズに強い制約が無いときは
(リングサイズが特定の値である必要が無く、一定以上であればよいとき)
リングサイズを2のるい乗とし、識別子にはリングサイズ-1とする。

当然知識としては知っているけど、
とっさにリングバッファを実装するときには実践できていなかったのでメモ。


以下はJavaの例

int[] buffer = new int[16];
for (int i=0; i<10000; i++) {
    buffer[i+10&15] = ...
}

ビット演算子(&)の優先順位は和(+)よりも低いので、
上記で(i+10)&15と同意であることも忘れやすいので注意。

もちろん、リングサイズを必要最低限だけ確保し、
リングサイズの剰余で識別子を算出しても処理内容は同じ。

int[] buffer = new int[12];
for (int i=0; i<10000; i++) {
    buffer[(i+10)%12] = ...
}

剰余(%)の優先順位は和(+)よりも高いので、
こちらは括弧が必須であることもビット演算子との違いであることに注意。


自分では可能な限り、るい乗・ビットマスクを用いた
実装が自然とできるようになりたい。