if文を使わずに、配列内の値が0以外の要素だけ、指定された値に上書きする方法

昔からある、ビット演算の魔術と呼ばれるような計算についでです。
有識者にとっては常識だと思うのですが、慣れていない自分の備忘録として残しておきます。

タイトルのような処理を素直に書く場合は、通常以下のようにif文を使って条件を判定します。

// 要素が6個の配列に値が入っている
BYTE data[6];
data[0] = 0x00;
data[1] = 0x66;
data[2] = 0x77;
data[3] = 0x88;
data[4] = 0x00;
data[5] = 0x99;

// 上記6個の値のうち値が0の要素以外を0xFFに上書きしたい場合
for ( int i=0; i < 6; ++i )
{
    if ( data[i] != 0 )
    {
        data[i] = 0xFF;
    }
}

配列の内容
data[0] => 0x00;
data[1] => 0xFF;
data[2] => 0xFF;
data[3] => 0xFF;
data[4] => 0x00;
data[5] => 0xFF;

私がこのような処理が必要になったのは、大きな画像に対して1ピクセル単位に
条件判定をし、かつリアルタイムに計算しなければいけないという状況でした。

もし60FPS(1秒間に60回更新)で、1024x768の画像の各ピクセルに処理を行う場合、
1秒間に60 * 1024 * 768 = 47,185,920回もの条件判定が発生してしまいます。

条件判定は最適化を妨げ、性能に多大な影響を与えてしまうため、
ビット演算を駆使してif文を排除する必要があります。

ビット演算を使用すると、上記コードは以下のようになります。

BYTE mask = 0;
for ( int i=0; i < 6; ++i )
{
    mask = data[i] | ( (data[i] & 0x7F) + 0x7F );
    mask = ( mask & 0x80 ) >> 7;
    mask = ( mask + 0x7F ) ^ 0x7F;

    data[i] = mask & 0xFF;
}

最終的には0のときは0x00、0以外のときは0xFFになるマスクを作成し、
上書きしたい値(ここでは0xFF)とのANDを取ることにより代入される値が0か0xFFになります。

最初の行は加算の敷衍化という方法を使用して0の場合だけ
MSB（最上位ビット）が1にならないような計算をしています。

次の行はMSB以外のビットを0にするため0x80でANDをとり、それをLSB（最下位ビット）に移動させます。

最後にLSBが1の場合は0x7Fが加算されると0x80(2進数で10000000)になるため、
0x7FとのXORを取ると0xFFになるというわけです。

LSBが0の場合は0x7Fを加算しても結果が0x7Fになるので、これに0x7FのXORをとれば
同じ値のXORなのですから、結果は当然0になります。

最後の行で代入したい値(0xFF)とANDをとって完了です。

最後に

2013年の最後に更新したかったので急ぎ足になってしまいました。。
後で見直してもう少し追加しようかと思ったのですが、数か月後に読んで
理解できたので、このままにしようかと思います。

来年はもう少し更新頻度を上げたいですね。

それでは皆様、よいお年を(^-^)/