8

我一直在想办法让我同时进行两次比较，以找到三个数字中最大/最小的一个。在这种情况下，对它们的算术运算被认为是“免费的”。

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

如果不是这种情况，是否可以使用两个比较？我在想也许可以以某种方式比较数字或他们的产品或其他东西的差异，但一无所获。

再次强调一下，仍然进行了两次比较，只是没有一个比较依赖于另一个比较的结果。

到目前为止很好的答案，谢谢大家

4

7 回答 7

5

忽略相等值（“关系”）的可能性，有 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比较时，您无法区分标有 的两种情况。（选择另一组两个比较当然会同样失败，（通过对称性））。

但遗憾的是：我们未能仅使用两个比特对三种可能的结果进行编码。（是的，我们可以，但我们需要第三次比较，或者根据第一次比较的结果选择第二次比较）

于 2013-11-06T21:01:49.737 回答
3

我认为这是可能的（根据问题的原始形式，以下是最小值）：

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

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

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 从它们的中点向下的距离的一半。这可以再次应用到 yield min(A,B,C)，但是你失去了最小值的身份，即你只知道最小值的值，但不知道它来自哪里。

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

于 2013-11-06T21:47:07.467 回答
1

如果您只是在谈论整数，我认为您可以使用一些数学和一些小提琴来进行零比较。给定三个 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 回答
0

来自Bit Twiddling Hacks

r = y ^ ((x ^ y) & -(x < y)); // min(x, y)

min = r ^ ((z ^ r) & -(z < r)); // min(z, r)

两个对比！

于 2013-11-06T21:43:03.030 回答
0

如何找到最小值：

If (b < a)
   Swap(a, b)

If (c < a)
   Swap(a, c)

Return a;
于 2013-11-06T21:43:30.793 回答
0

理论上，您可以通过零比较来做到这一点，假设 2 的补数表示（并且右移有符号数会保留其符号）。

    min(a, b) = (a+b-abs(a-b))/2
    abs(a) = (2*(a >> bit_depth)+1) * a

接着

    min(a,b,c) = min(min(a,b),c)

这是有效的，因为假设a >> bit_depth给出0正数和-1负数，然后2*(a>>bit_depth)+1给出1正数和-1负数。这给出了signum函数，我们得到abs(a) = signum(a) * a.

那么这只是 min(a,b) 公式的问题。这可以通过两种可能性来证明：

    case min(a,b) = a:
    min(a,b) = (a+b - -(a-b))/2
    min(a,b) = (a+b+a-b)/2
    min(a,b) = a

    case min(a,b) = b:
    min(a,b) = (a+b-(a-b))/2
    min(a,b) = (a+b-a+b)/2
    min(a,b) = b

所以 min(a,b) 的公式有效。

上述假设仅适用于该abs()函数，如果您可以abs()为您的数据类型获得一个 0 比较函数，那么您就可以开始了。

例如，IEEE754 浮点数据有一个符号位作为最高位，因此绝对值只是意味着清除该位。这意味着您也可以使用浮点数。

然后您可以在 0 次比较中将此扩展到minN 个数字。

但在实践中，很难想象这种方法会击败任何不是故意变慢的方法。这都是关于使用少于 3 次独立比较，而不是在实践中比直接实现更快。

于 2013-11-06T21:49:13.400 回答
0 
if cos(1.5*atan2(sqrt(3)*(B-C), 2*A-B-C))>0 then 
  A is the max
else
  if cos(1.5*atan2(sqrt(3)*(C-A), 2*B-C-A))>0  then 
    B is the max
  else                   
    C is the max
于 2013-11-07T00:41:01.257 回答