C语言 在不使用条件语句和三元运算符的情况下，在 C 中查找最多三个数字
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/7074010/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Find maximum of three number in C without using conditional statement and ternary operator
提问by Microsoft Developer
I have to find maximum of three number provided by user but with some restrictions. Its not allowed to use any conditional statement. I tried using ternary operator like below.
我必须找到用户提供的最多三个数字，但有一些限制。它不允许使用任何条件语句。我尝试使用如下所示的三元运算符。
max=(a>b?a:b)>c?(a>b?a:b):c
But again its restricted to use ternary operator. Now I am not getting any idea how to do this?
但再次限制使用三元运算符。现在我不知道该怎么做？
回答by Nawaz
Taking advantage of short-circuiting in boolean expressions:
利用布尔表达式中的短路：
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;
}
Explanation:
解释：
In boolean ANDoperation such as x && y, y is evaluated if and only ifxis true. If xis false, then yis not evaluated, because the whole expression would be false which can be deduced without even evaluating y. This is called short-circuiting when the value of a boolean expression can be deduced without evaluating all operands in it.
在AND诸如 的布尔运算中x && y，当且仅当x为真时才对 y 求值。如果x为假，y则不求值，因为整个表达式都是假的，甚至无需求值就可以推导出来y。当可以在不评估其中的所有操作数的情况下推导出布尔表达式的值时，这称为短路。
Apply this principle to the above code. Initially mis a. Now if (m < b)is true, then that means, bis greater than m(which is actually a), so the second subexpression (m = b)is evaluated and mis set to b. If however (m < b)is false, then second subexpression will not be evaluated and mwill remain a(which is greater than b). In a similar way, second expression is evaluated (on the next line).
将此原则应用于上述代码。最初m是a。现在，如果 (m < b)为真，则表示b大于m（实际上是a），因此计算第二个子表达式 (m = b)并将m其设置为b。但是(m < b)，如果为 false，则不会计算第二个子表达式m并将保留a（大于b）。以类似的方式，计算第二个表达式（在下一行）。
In short, you can read the expression (m < x) && (m = x)as follows : set mto xif and only ifmis less than xi.e (m < x)is true. Hope this helps you understanding the code.
简而言之，您可以(m < x) && (m = x)按如下方式阅读表达式：设置m为x当且仅当m小于xie(m < x)为真。希望这有助于您理解代码。
Test code:
测试代码：
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;
}
Output:
输出：
3
3
3
Note the implementation of maxgives warnings because evaluated expressions are not used:
请注意max给出警告的实现，因为未使用评估表达式：
prog.c:6: warning: value computed is not used
prog.c:7: warning: value computed is not used
prog.c:6：警告：未使用计算值
prog.c:7：警告：未使用计算值
To avoid these (harmless) warnings, you can implement maxas:
为了避免这些（无害的）警告，您可以实现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;
}
The trick is that now we're casting the boolean expressions to void, which causes suppression of the warnings:
诀窍是现在我们将布尔表达式转换为void，这会导致警告的抑制：
回答by Foo Bah
Assuming you are dealing with integers, how about:
假设您正在处理整数，那么如何：
#define max(x,y) (x ^ ((x ^ y) & -(x < y)))
int max3(int x, int y, int z) {
return max(max(x,y),z);
}
回答by David Rodríguez - dribeas
Just to add another alternative to avoid conditional execution (which is not the one I would use, but seemed missing from the set of solutions):
只是添加另一种替代方法以避免条件执行（这不是我会使用的方法，但似乎在解决方案集中缺失）：
int max( int a, int b, int c ) {
int l1[] = { a, b };
int l2[] = { l1[ a<b ], c };
return l2[ l2[0] < c ];
}
The approach uses (as most others), the fact that the result of a boolean expression when converted to int yields either 0 or 1. The simplified version for two values would be:
该方法使用（与大多数其他方法一样），布尔表达式的结果在转换为 int 时产生 0 或 1 的事实。两个值的简化版本将是：
int max( int a, int b ) {
int lookup[] { a, b };
return lookup[ a < b ];
}
If the expression a<bis correct we return b, carefully stored in the first index of the lookup array. If the expression yields false, then we return athat is stored as element 0of the lookup array. Using this as a building block, you can say:
如果表达式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 ];
}
Which can be trivially transformed to the code above by avoiding the second call to the inner maxusing the result already stored in lookup[0]and inlining the original call to max(int,int).
通过max使用已经存储在中的结果避免对内部的第二次调用lookup[0]并将原始调用内联到max(int,int).
(This part is just another proof that you have to measure before jumping into conclusions, see the edit at the end)
（这部分只是你在得出结论之前必须衡量的另一个证明，请参阅最后的编辑）
As to which would I actually use... well, probably the one by @Foo Baa heremodified to use an inline function rather than a macro. The next option would be either this one or the one by @MSN here.
至于我实际使用哪个......好吧，可能是@Foo Baa在这里修改为使用内联函数而不是宏。下一个选项要么是这个，要么是@MSN here的那个。
The common denominator of these three solutions not present in the accepted answer is that they do not only avoid the syntactic construct of ifor the ternary operator ?:, but that they avoid branchingaltogether, and that can have an impact in performance. The branch-predictorin the CPU cannot possibly miss when there are no branches.
已接受的答案中没有出现的这三个解决方案的共同点是，它们不仅避免了if或 三元运算符的句法构造?:，而且完全避免了分支，这会对性能产生影响。当没有分支时，CPU 中的分支预测器不可能丢失。
When considering performance, first measure then think
在考虑性能时，先衡量再考虑
I have actually implemented a few of the different options for a 2-way max, and analyzed the generated code by the compiler. The following three solutions generate all the same assembly code:
我实际上已经为 2-way max 实现了一些不同的选项，并分析了编译器生成的代码。以下三个解决方案生成所有相同的汇编代码：
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;
}
Which is not surprising, since all of the three represent the exact same operation. The interesting bit of information is that the generated code does not contain any branch. The implementation is simple with the cmovgeinstruction (test carried out with g++ in an intel x64 platform):
这并不奇怪，因为所有三个都代表完全相同的操作。有趣的一点是生成的代码不包含任何分支。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
The trick is in the conditional move instruction, that avoids any potential branch.
诀窍在于条件移动指令，它避免了任何潜在的分支。
None of the other solutions has any branches, but all of them translate to more cpu instructions than any of this, which at the end of the day reassures us that we should always write simple codeand let the compiler optimize it for us.
其他解决方案都没有任何分支，但所有这些都转换为比任何一个都多的 cpu 指令，这最终让我们放心，我们应该始终编写简单的代码并让编译器为我们优化它。
回答by Keith Thompson
UPDATE:Looking at this 4 years later, I see that it fails badly if two or more of the values happen to be equal. Replacing >by >=changes the behavior, but doesn't fix the problem. It might still be salvageable, so I won't delete it yet, but don't use this in production code.
更新：4 年后看这个，我发现如果两个或多个值碰巧相等，它会严重失败。更换>通过>=改变行为，但并没有解决问题。它可能仍然可以挽救，所以我不会删除它，但不要在生产代码中使用它。
Ok, here's mine:
好的，这是我的：
int max3(int a, int b, int c)
{
return a * (a > b & a > c) +
b * (b > a & b > c) +
c * (c > a & c > b);
}
Note that the use of &rather than &&avoids any conditional code; it relies on the fact that >always yields 0 or 1. (The code generated for a > bmight involve conditional jumps, but they're not visible from C.)
请注意，使用&而不是&&避免任何条件代码；它依赖于>总是产生 0 或 1的事实。（生成的代码a > b可能涉及条件跳转，但它们在 C 中不可见。）
回答by MSN
int fast_int_max(int a, int b)
{
int select= -(a < b);
unsigned int b_mask= select, a_mask= ~b_mask;
return (a&a_mask)|(b&b_mask);
}
int fast_int_max3(int a, int b, int c)
{
return fast_int_max(a, fast_int_max(b, c));
}
回答by gsk
Boolean valued operators (including <, &&, etc) typically translate to conditional operations at the machine code level, so don't fulfill the spirit of the challenge. Here's a solution that any reasonable compiler would translate to only arithmetic instructions with no conditional jumps (assuming long has more bits than int and that long is 64 bits). The idea is that "m" captures and replicates the sign bit of b - a, so m is either all 1 bits (if a > b) or all zero bits (if a <= b). Note that long is used to avoid overflow. If for some reason you know that b - a doesn't over/under-flow, then the use of long isn't needed.
布尔值运算符（包括 <、&& 等）通常在机器代码级别转换为条件操作，因此不要满足挑战的精神。这是一个解决方案，任何合理的编译器都会将其转换为没有条件跳转的算术指令（假设 long 的位比 int 多，并且 long 是 64 位）。这个想法是“m”捕获并复制 b - a 的符号位，所以 m 要么全为 1（如果 a > b）要么全为零（如果 a <= b）。请注意，使用 long 是为了避免溢出。如果由于某种原因您知道 b - a 不会溢出/下溢，则不需要使用 long 。
int max(int a, int b)
{
long d = (long)b - (long)a;
int m = (int)(d >> 63);
return a & m | b & ~m;
}
int max(int a, int b, int c)
{
long d;
int m;
d = (long)b - (long)a;
m = (int)(d >> 63);
a = a & m | b & ~m;
d = (long)c - (long)a;
m = (int)(d >> 63);
return a & m | c & ~m;
}
回答by Lee Louviere
No conditionals. Only a cast to uint. Perfect solution.
没有条件。只有一个演员表。完美的解决方案。
int abs (a) { return (int)((unsigned int)a); }
int max (a, b) { return (a + b + abs(a - b)) / 2; }
int min (a, b) { return (a + b - abs(a - b)) / 2; }
void sort (int & a, int & b, int & c)
{
int max = max(max(a,b), c);
int min = min(min(a,b), c);
int middle = middle = a + b + c - max - min;
a = max;
b = middle;
c = min;
}
回答by user5243048
You can use this code to find largest out of two:
您可以使用此代码从两个中找出最大的：
max{a,b} = abs(a-b)/2 + (a+b)/2
then use it again to find the third number:
然后再次使用它来查找第三个数字：
max{a,b,c} = max(a,max(b,c))
See that this works for positive numbers you can change it to work for negative as well.
看到这适用于正数，您可以将其更改为也适用于负数。
回答by Khaled AbuShqear
#include "stdafx.h"
#include <iostream>
int main()
{
int x,y,z;
scanf("%d %d %d", &x,&y, &z);
int max = ((x+y) + abs(x-y)) /2;
max = ((max+z) + abs(max-z)) /2;
printf("%d ", max);
return 0;
}
回答by mok
No conditional statements, just loops and assignments. And completely different form others' answers :)
没有条件语句，只有循环和赋值。与其他人的答案完全不同:)
while (a > b)
{
while (a > c)
{
tmp = a;
goto finish;
}
tmp = c;
goto finish;
}
while (b > c)
{
tmp = b;
goto finish;
}
tmp = c;
finish: max = tmp;
