[解決済み] if-elseや他の比較演算子を使わずに2つの整数の最大値を求めるこのスニペットを説明してください。

質問

2つの数値の最大値を求めよ。if-elseや他の比較演算子は使ってはいけない。ネットの掲示板でこの質問を見つけたので、StackOverflowで質問してみようと思います。

例題 入力。5, 10 出力 10

私はこの解決策を見つけました。どなたか、これらのコードの行を理解するのを助けていただけませんか。

int getMax(int a, int b) {  
    int c = a - b;  
    int k = (c >> 31) & 0x1;  
    int max = a - k * c;  
    return max;  
}

どのように解決するのですか？

int getMax(int a, int b) {
    int c = a - b;
    int k = (c >> 31) & 0x1;
    int max = a - k * c;
    return max;
}

これを分解してみましょう。 この最初の行は簡単そうに見えます。 a と b . の場合、この値は負になります。 a < b の場合は負で、それ以外の場合は非負である。しかし、実はここにバグがある。もし、数値の差が a と b が整数に収まらないほど大きい場合、これは未定義の動作につながります - おっと！？ということで、ここではそうならないことを前提にしましょう。

次の行で、これは

int k = (c >> 31) & 0x1;

の値をチェックすることです。 c が負であるかどうかを調べることです。 事実上すべての現代のコンピュータでは、数値は 2の補数 と呼ばれる形式で保存され、数値の最上位ビットが正の場合は 0、負の場合は 1 になります。 さらに、ほとんどの int は 32 ビットである。 (c >> 31) は、数値の最上位ビットを最下位ビットの場所に残したまま、数値を31ビット下にシフトします。 次のステップでは、この数字を取り出し、1（その2進表現は最後のビット以外すべて0）と AND 演算することで、上位ビットをすべて消去し、最下位ビットだけを取得します。 の最下位ビットは c >> 31 の最上位ビットである c の最上位ビットを読み取ります。 c の最上位ビットを 0 か 1 のどちらかとして読み取ります。 最上位ビットが1である場合 c が1であれば最上位ビットは1なので、これは c が負(1)であるか正(0)であるかをチェックする方法である。 この理屈と上記の理屈を組み合わせると k が1であれば a < b の場合は1、それ以外の場合は0となります。

最終的にはこうなります。

int max = a - k * c;

もし a < b であれば k == 1 となり k * c = c = a - b というように

a - k * c = a - (a - b) = a - a + b = b

というのは、正しい最大値です。 a < b . そうでなければ、もし a >= b であれば k == 0 となり

a - k * c = a - 0 = a

というのも正しい最大値です。