算法求return最大数不带IF

Question

在求职面试中，我的朋友不得不解决这个问题：

Develop an algorithm that receives two variables, a and b both integer and returns the largest.

Example: If a = 2 and b = 7 the algorithm returns 7.

Restrictions:
- You can not use IF's not anything that comparison;
- Also one can not use Math or colections type libraries, because internally they use IF's;
- You can not use ternary operator, it is an IF.

这是最后一个问题，页面底部有以下句子：

Do not look for perfection, just do the best you can.

我们不知道这是一个提示还是一个励志短语。

没有提到或要求特定语言，那么我猜可以使用伪代码或者是逻辑问题。

这里有几个程序员，没有人设法解决。

Answer 1

既然没有明确说明语言，那就选择X86汇编吧！

CMP EAX, EBX;   <-- assuming that A is stored in EAX and B is stored in EBX
CMOVL EAX, EBX; <-- no branching required

[编辑：]如果 CMP 被认为是 IF 的一部分，我们可以使用第三个寄存器并执行 SUB，这绝对不是：

MOV EDX, EAX;
SUB EDX, EBX;
CMOVL EAX, EBX;

Answer 2

你可以将一些东西存储在一个临时变量中并尝试这样的事情：

解决方案来自：- Find maximum of three number in C without using conditional statement and ternary operator

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 AND operation such as x && y, y is evaluated if and only if x is true. If x is false, then y is 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.

Apply this principle to the above code. Initially m is a. Now if (m < b) is true, then that means, b is greater than m (which is actually a), so the second subexpression (m = b) is evaluated and m is set to b. If however (m < b) is false, then second subexpression will not be evaluated and m will remain a (which is greater than b). In a similar way, second expression is evaluated (on the next line).

In short, you can read the expression (m < x) && (m = x) as follows : set m to x if and only if m is less than x i.e (m < x) is true. Hope this helps you understanding the code.

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 Online Demo: http://www.ideone.com/8045P

Note the implementation of max gives warnings because evaluated expressions are not used:

prog.c:6: warning: value computed is not used prog.c:7: warning: value computed is not used To avoid these (harmless) warnings, you can implement max as:

 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:

http://www.ideone.com/PZ1sP

Answer 3

这是 Julia 中的一个解决方案，它应该非常清晰并且适用于任何 64 位数据类型。它没有任何控制流或布尔值，只有算术运算和位移。

function f(a,b)
  diff = reinterpret(UInt64,a-b)
  sgn = reinterpret(typeof(a),diff >> 63) #Sign bit of (a-b).
  return (a - sgn*a) + sgn*b
end

Answer 4

(a + b + abs(a-b)) / 2

-- 必须接近可接受。当然 abs() 可以在没有任何 if 语句的情况下实现，你只需要将符号位设置为 0.

Answer 5

伙计们感谢您的帮助。我有机会查看他们正在寻找的答案。
由于它要求算法，它不能使用某种编程语言的函数。

答案是： (a+b+|a-b|) * 0,5

BUT 正如我之前在同一个 post 中评论的那样，|a-b| 或 abs(a-b) 被认为是一个 IF，因为它们测试是否该数字是否为负数。

完整的正确答案 必须在不使用 IF 的情况下实现函数 abs(a-b) 或 |a-b|，然后答案才会完整。

我已经在搜索数学属性和绝对值的演示来解决这个问题，但是如果您发现只用简单的数学就可以实现它，那将非常有帮助。

[编辑] 如果我这样做：√((a-b)^2)。是否需要数学图书馆？

算法求return最大数不带IF

Algorithm to return the largest number without IF

algorithm

logic

if-statement

return

restriction