在不使用条件语句和三元运算符的情况下,在C中最多找到三个数字

Question

我必须找到最多由用户提供的三个号码,但有一些限制.不允许使用任何条件声明.我尝试使用下面的三元运算符.

max=(a>b?a:b)>c?(a>b?a:b):c

但它再次限制使用三元运算符.现在我不知道该怎么做？

Answer 1

利用布尔表达式中的短路:

int max(int a, int b, int c)
{
     int m = a;
     (m < b) && (m = b); //these are not conditional statements.
     (m < c) && (m = c); //these are just boolean expressions.
     return m;
}

说明:

在AND诸如的布尔运算中x && y,当且仅当if x为真时,才计算y .如果x为false,y则不进行求值,因为整个表达式都是false,可以在不进行求值的情况下推导出y.当可以推导出布尔表达式的值而不评估其中的所有操作数时,这称为短路.

将此原则应用于上述代码.最初m是a.现在,如果 (m < b)为真,则表示b大于m(实际上a),因此第二个子表达式 (m = b)被计算并m设置为b.如果(m < b)是假的,那么第二个子表达式将不会被评估m并将保留a(大于b).以类似的方式,评估第二个表达式(在下一行).

简而言之,您可以(m < x) && (m = x)按如下方式读取表达式:设置m为x if且仅当if m小于xie时(m < x)为true.希望这有助于您理解代码.

测试代码:

int main() {
        printf("%d\n", max(1,2,3));
        printf("%d\n", max(2,3,1));
        printf("%d\n", max(3,1,2));
        return 0;
}

输出:

3
3
3

请注意执行max提供警告,因为未使用计算表达式:

prog.c:6:警告:未使用计算值
prog.c:7:警告:未使用计算值

要避免这些(无害)警告,您可以实现max:

int max(int a, int b, int c)
{
     int m = a;
     (void)((m < b) && (m = b)); //these are not conditional statements.
     (void)((m < c) && (m = c)); //these are just boolean expressions.
     return m;
}

诀窍是,现在我们将布尔表达式转换为void,这会导致警告的抑制:

Answer 2

假设你正在处理整数,那么:

#define max(x,y) (x ^ ((x ^ y) & -(x < y)))
int max3(int x, int y, int z) {
    return max(max(x,y),z);
}

Answer 3

只是添加另一个替代方法来避免条件执行(这不是我会使用的,但似乎从解决方案集中缺失):

int max( int a, int b, int c ) {
   int l1[] = { a, b };
   int l2[] = { l1[ a<b ], c };
   return l2[ l2[0] < c ];
}

该方法使用(和大多数其他方法一样),当转换为int时,布尔表达式的结果产生0或1.两个值的简化版本将是:

int max( int a, int b ) {
   int lookup[] { a, b };
   return lookup[ a < b ];
}

如果表达式a<b是正确的,我们返回b,小心地存储在查找数组的第一个索引中.如果表达式产生false,那么我们返回a它作为0查找数组的元素存储.使用它作为构建块,您可以说:

int max( int a, int b, int c ) {
   int lookup[ max(a,b), c ];
   return lookup[ max(a,b) < c ];
}

通过避免max使用已存储的结果lookup[0]并内联原始调用来对内部进行第二次调用,可以将其简单地转换为上面的代码max(int,int).

(这部分只是另一个证据,你必须在得出结论之前进行测量,最后看编辑)

至于我实际使用哪个......好吧,可能是@Foo Baa 在这里修改为使用内联函数而不是宏.下一个选择是,要么这一个或一个由@MSN 这里.

在接受的答案中没有出现的这三种解决方案的共同点是它们不仅避免了句法结构if或三元运算符?:,而且它们完全避免了分支,并且可能对性能产生影响.当没有分支时,CPU中的分支预测器不可能错过.

在考虑表现时,首先要考虑一下

实际上,我实现了一些双向最大的不同选项,并由编译器分析生成的代码.以下三个解决方案生成所有相同的汇编代码:

int max( int a, int b ) { if ( a < b ) return b; else return a; }
int max( int a, int b ) { return (a < b? b : a ); }
int max( int a, int b ) {
   (void)((a < b) && (a = b));
   return a;
}

这并不奇怪,因为这三者都代表完全相同的操作.有趣的信息是生成的代码不包含任何分支.使用cmovge指令(在intel x64平台中使用g ++进行测试)的实现很简单:

movl    %edi, %eax       # move a into the return value
cmpl    %edi, %esi       # compare a and b
cmovge  %esi, %eax       # if (b>a), move b into the return value
ret

诀窍在于条件移动指令,避免任何潜在的分支.

其他解决方案都没有任何分支,但它们都转换为比任何更多的cpu指令,这些指令在一天结束时向我们保证我们应该总是编写简单的代码并让编译器为我们优化它.

Answer 4

更新:看看这4年后,我发现如果两个或多个值恰好相等,它就会失败.>通过>=更改行为来替换,但不能解决问题.它可能仍然可以挽救,所以我不会删除它,但不要在生产代码中使用它.

好的,这是我的:

int max3(int a, int b, int c)
{
    return a * (a > b & a > c) +
           b * (b > a & b > c) +
           c * (c > a & c > b);
}

注意使用&而不是&&避免任何条件代码; 它依赖于>总是产生0或1 的事实.(生成的代码a > b可能涉及条件跳转,但它们在C中不可见)