3つの整数のうち最大の奇数を返す

code:c++

// 32bitの整数a, b, cを受け取り、その中から最大の奇数を返す

// a, b, cのうち少なくとも1つの値が奇数であると保証されているとする。

int oddmax3(int a, int b, int c){

int d = a - (((((a - b) >> 31) & (-(b & 1))) | ((a & 1) - 1)) & (a - b));

int e = d - (((((d - c) >> 31) & (-(c & 1))) | ((d & 1) - 1)) & (d - c));

return e;

}

3つ同時に考えるのは難しいので2つずつ処理した

oddmax2(a,b)を考える。bを返す場合はa-(a-b)、aを返す場合はa-0となるように、a-bを0xffffffffまたは0でマスクする。

bが奇数かつa<b

aが偶数

のどちらかを満たせばb、そうでなければaを返せば良い。(aもbも偶数ならaが返る)

そこで、bを返す場合に0xffffffff、aを返す場合に0となるマスクを作る。それぞれの条件は

(-(b&1)) & ((a-b) >> 31)

(a & 1) - 1

と書き下せるので、これらのORを取るとマスクが完成する。

ちなみに、負の数を右シフトすると上位ビットに1が挿入される。これによって(a-b) >> 31は、a>bであれば0、a<bであれば0xffffffffとなる。この方法はとても頭が良い。

ただ、もしかしたら負の数の右シフトで0が挿入される場合があるかもしれないので、言語仕様などを確認すべき。

2023/11/09追記

code:c++

b & (b > a)

がb>aかつbが奇数のときに1になるので、これを使うと

code:c++

int oddmax3(int a, int b, int c){

int d = a - ((-(b & (b > a)) | ((a & 1) - 1)) & (a - b));

int e = d - ((-(c & (c > d)) | ((d & 1) - 1)) & (d - c));

return e;

}

で済む。美しい！

ちなみに、比較演算子を使わなくても、b>aの代わりに符号ビットを使うのでも良さそう。でもコード長は元のとそんなに変わらない…

code:c++

int oddmax3(int a, int b, int c){

int d = a - ((-(b & ((a - b) >> 31) & 1) | ((a & 1) - 1)) & (a - b));

int e = d - ((-(c & ((d - c) >> 31) & 1) | ((d & 1) - 1)) & (d - c));

return e;

}

2023/11/09追記

この問題は「偶数の引数を-INFにしてしまい、それからMAXを取る」と言い換えることもできるので、それを使う方法もある。