Algorithm to return the largest number without IF

Question

On a job interview my friend had to solve this Problem:

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.

It was the last question and at bottom of the page had the following sentence:

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

We don't know if it's a hint or just a motivational phrase.

It is not mentioned or required a specific language, then i guess that can be used pseudocode or is a logic problem.

Here are several programmers, no one managed to solve.

Answer 1

Here's one solution in Julia which should be quite clear and works with any 64-bit data type. It does not have any control flow or booleans, just arithmetic operations and bitshifts.

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 2

you can store something in a temporary variable and try something like this:

Solution from:- 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

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

-- that must be close to acceptable. Surely abs() can be implemented without any if statements, you just have to set the sign bit to 0.

Answer 4

Since the language is not stated explicitly, let`s pick X86 assembly!

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

[EDIT:] In case CMP is considered a part of IF, we can take a third register and perform a SUB, which is definitely not:

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

Answer 5

Guys thanks for the help. I had the opportunity to check the answer they were looking for.
As it's requested an algorithm it cannot use a function of a certain programming language.

The answer is: (a+b+|a-b|) * 0,5

BUT as I commented before in this same post, the |a-b| or abs(a-b) are considered an IF, because they test if the number is negative or not.

The complete right answer must implement the function abs(a-b) or |a-b|without using IF's, then the answer will be complete.

I am already searching for math properties and demosntrations of the absolute value to solve this, but if you find anyway to implement this with only simple math it would be very helpful.

[Edit] If I do this: √((a-b)^2). Would it be necessary math library?