8

私は、2 つの比較を同時に行って、3 つの数値の最大/最小を見つける方法を考え出そうとしています。この場合、それらの算術演算は「無料」と見なされます。

つまり、2 のうち大きい方を見つけてから 3 番目の数値と比較する従来の方法は、この場合は有効ではありません。これは、一方の比較が他方の結果に依存するためです。

そうでない場合に 2 つの比較を使用することは可能ですか? 数字の違いをどうにか比較したり、製品の違いを比較したりと考えていたのですが、何も思いつきませんでした。

もう一度強調しておきますが、どちらの比較ももう一方の比較の結果に依存していないというだけで、2 つの比較が引き続き行われます。

これまでのところ素晴らしい答えです、ありがとう

4

7 に答える 7

5

等しい値 (「同点」) の可能性を無視すると、3 つあります。:= 3 つのアイテムの 6 つの可能な順序。比較が正確に 1 ビットを生成する場合、2 つの比較は 2*2 := 4 の可能な構成のみをエンコードできます。4 < 6. IOW: 2 つの固定比較を使用して 3 つの項目の順序を決定することはできません。

真理値表の使用:

a b c|min|a<b a<c b<c| condition needed using only a<b and a<c
-+-+-+---+---+---+---+------------------
1 2 3| a | 1   1   1 | (ab==1 && ac==1)
1 3 2| a | 1   1   0 |  ...
2 1 3| b | 0   1   1 | (ab==0 && ac==1)
3 1 2| b | 0   0   1 | (ab==0 && ac==0) <<--- (*)
2 3 1| c | 1   0   0 | (ab==1 && ac==0)
3 2 1| c | 0   0   0 | (ab==0 && ac==0) <<--- (*)

ご覧のとおり、との比較(*)のみを使用すると、 でマークされた 2 つのケースを区別できません。(2 つの比較の別のセットを選択すると、(対称性により) もちろん同様に失敗します)。a<ba<c

しかし残念なことに、2ビットのみを使用して3 つの可能な結果を​​エンコードできませんでした。(はい、できますが、3 番目の比較が必要になるか、最初の比較の結果に基づいて 2 番目の比較を選択する必要があります)

于 2013-11-06T21:01:49.737 に答える
1

整数だけを話している場合は、数学と少しフィドルを使用してゼロ比較でそれを行うことができると思います。3 つの int 値 a、b、および c が与えられた場合:

int d = ((a + b) - Abs(a - b)) / 2; // find d = min(a,b)
int e = ((d + c) - Abs(d - c)) / 2; // find min(d,c)

Abs(x) を次のように実装

int Abs(int x) {
    int mask = x >> 31;
    return (x + mask) ^ mask;
}

広範囲にテストされていないため、何かを見落としている可能性があります。Abs ビット ツイドルの功績は、これらの情報源に帰属します。

整数絶対値の計算方法

http://graphics.stanford.edu/~seander/bithacks.html#IntegerAbs

于 2013-11-06T21:44:48.597 に答える