ビット演算について考える機会があったので、結果をまとめておきます。
a と b は それぞれ 32 bit の unsigned long の変数で、これに 1 byte の 整 数が 4つまとめて入っているとします。これらについて、飽和加算をすることを 考えます。飽和加算とは、和が 0xff を越えたら結果を 0xff にするものです。
結果から先に出すと、次のような式になります。
tmp = ((a & b) + (((a ^ b) >> 1) & 0x7f7f7f7f)) & 0x80808080; // (1) mask = (tmp << 1) - (tmp >> 7); // (2) result = ((a + b) - mask) | mask; // (3)
なぜこうなるのかについて解説します。
mask とは、オーバーフローしたバイトは 0xff で、それ以外のバイトは 0x00 であるようなマスクです。(*)
このような mask が与えられていたとすると、飽和加算の結果は (3) 式で求めることができます。
まず、a + b で二つの数を加えます。もしオーバーフローがなければこれでかま わないのですが、オーバーフローしたバイトがあった場合、このままだと、オー バーフローが生じたバイトの上位のバイトに影響が及んでしまうので、これを戻 さなくてはなりません。この影響をなくしているのが mask を引いている項です。 オーバーフローが生じたバイトから 0xff を引いているので、上位バイトに繰り 上がった分は差し引かれて元に戻ります。繰り上がりが生じたバイト自体は値が ずれてしまいますが、それを 0xff にそろえるのが、 mask と or を取る項です。
これにより、(*) のような mask が計算されていれば、飽和加算の計算ができる ことが分かりました。では、mask はどうやって計算すればいいのでしょうか。
mask を計算しているのが (1) 式と (2) 式です。(1) 式の理解のポイントは、 (a & b) + ((a ^ b) >> 1) という値が (a + b) >> 1 に等しいということです。 0x7f7f7f7f と and を取っているのは、隣りのバイトのビットが混ざらないよう にするためです。すなわち、tmp には、各バイトの和を右 1 bit シフトさせた 数の 8 bit 目だけが入っています。これは、各バイトの和 の 9 bit 目に等し いです。すなわち、各バイトの和がオーバーフローしたかどうかのフラグになり ます。 (オーバーフローした場合のみ、9 bit 目が 1 になるので)
このとき、tmp のビット配列は
W0000000 X0000000 Y0000000 Z0000000
という値になっています。(W, X, Y, Z は、そのバイトの和がオーバーフローしたかどうかのフラグで、 0 か 1)
ここから、
WWWWWWWW XXXXXXXX YYYYYYYY ZZZZZZZZ
というマスクを作成しているのが (2) 式です。
ポイントは、
(0x80 << 1) - (0x80 >> 7) = 0xff (0x00 << 1) - (0x00 >> 7) = 0x00
ということです。