1

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.

Improve this question
1

5 Answers 5

Reset to default
3

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
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

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

Improve this answer

5 Comments

I guess '<' and all comparison operators are considered a kind of 'IF' because it 'returns a bollean' in its Implementation
so now you are basically saying that we can't even use relational operators
although i don't think there is any other way if you remove the relational operators also btw you can also check out geeksforgeeks.org/…
i don't know the right answer.. You got a point because if we can't use them, the expression ( a + b + |a-b| )/2 will also be incorrect. The absolute value has an if inside. If a > 0 than a elseif a< 0 than -a
I once saw a program similar to this kind of situation the problem was that the printf() was predefined and contained only one variable and the interviewer asked the person to write a program using that printf to print all numbers from 1 to 100 without using recursion,loops,goto or other multiple printf.
1 
(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.

Improve this answer

1 Comment

For the great justice: just zeroing a sign bit won`t help in the case of 2-s complement integers. But for IEEE floats this is indeed the right thing to do.
0

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;
Improve this answer

4 Comments

cmp is again if it just that u changed the language
Rule 1: "...not anything that [does a] comparison".
@neoR, riiiight. Edited.
I guess that solution with just a math expression its enough
0

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?

Improve this answer

5 Comments

As a comment in another answer pointed out, getting the absolute value of an IEEE float is a matter of clearing the sign bit. Getting the absolute value of a two's complement integer would be somewhat more involved if you can't use conditionals.
And that would have to be done at the lowest levels of programming right?
You could do it in C. You can cast the float to an int and set the high bit to 0. For integral data types, you should be able to do it with bitwise operators in any language.
See my answer, which shows how to take the absolute value of an integer, without using any conditionals.
Thanks @JimMischel! I guess that is right. I have looked the possible duplicated question that you marked and I understood it. I will close this post then. Thanks again. How can I delete it?

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.