是否可以通过同时使用两个比较来计算三个数字的最小值？

Question

我一直试图想出一些方法,我可以同时进行两次比较,以找到最大/最少的三个数字.在这种情况下,对它们的算术运算被认为是"自由的".

也就是说,找到两个中较大者的经典方法,然后将其与第三个数字进行比较在这种情况下无效,因为一个比较取决于另一个的结果.

在不是这种情况下,是否可以使用两个比较？我想也许可以比较某些数字或其产品或某些东西的数字差异,但却没有提出任何结论.

再强调一下,仍然进行了两次比较,只是两种比较都不依赖于另一种比较的结果.

到目前为止很棒的答案,谢谢你们

Answer 1

无视同等价值的可能性("关系"),有3个!:= 6个可能的三个项目的排序.如果比较恰好产生一位,那么两次比较只能编码2*2:= 4种可能的配置.并且4 <6.IOW:你不能使用两个固定的比较来决定三个项目的顺序.

使用真值表:

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) <<--- (*)

如您所见,(*)当仅使用a<b和a<c比较时,您无法区分标记的两种情况.(选择另一组两个比较当然会失败,(通过对称)).

但可惜的是:我们没有编码的3个使用两种可能的结果位.(是的,我们可以,但我们需要第三次比较,或者根据第一次比较的结果选择第二次比较)

Answer 2

我认为是有可能的（以下为min，根据问题的原始形式）：

B_lt_A = B < A
C_lt_min_A_B = C < (A + B - abs(A - B)) / 2

然后你将它们组合起来（我必须按顺序编写，但这实际上是一个三向开关）：

if (C_lt_min_A_B) then C is the min
else if (B_lt_A)  then B is the min
else                   A is the min

您可能会认为这abs()意味着比较，但这取决于硬件。有一个技巧可以在不比较整数的情况下做到这一点。对于 IEEE 754 浮点，只需将符号位强制为零即可。

关于(A + B - abs(A - B)) / 2： 这是(A + B) / 2 - abs(A - B) / 2，即 A 和 B 的最小值是 A 和 B 从中点向下的距离的一半。这可以再次应用以产生 min(A,B,C)，但是这样你就失去了最小值的身份，即，你只知道最小值的值，但不知道它来自哪里。

有一天，我们可能会发现，在某些情况下，并行进行 2 个比较可以提供更好的周转时间，甚至吞吐量。谁知道呢，也许是为了一些矢量化，或者为了一些 MapReduce，或者是为了一些我们还不知道的东西。