Find maximum of three number in C without using conditional statement and ternary operator

Question

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?

Knout

This definitely falls in the "unlikely to help anyone in the future" category (unless they're a student of an incompetent educator). Use the tools you have, this sort of question indicates that your course is probably a waste of time. – Kiddy

@paxdiablo. Its not wastage of time. Rather its good challenge. There are some possible ways but restricted so challenge to find new ways.. – Knout

This smells like homework. I have an interesting solution, which I'll post after the assignment is due. – Objurgate

@Keith: does it involve bitops? Check my response – Antechamber

@paxdiablo: I think that's a bit harsh. From the answer given it does sound like a good way to make the point about short circuit evaluation of boolean operators. – Pseudonymous

@Chirag, a challenge with no useful result is a useless challenge. In what piece of real world code would you ever use such a beast? You'd be tarred and feathered at a code review. John, if you want to teach someone about short circuit ops, there are better ways than using dubious puzzles. – Kiddy

@paxdiablo: Such puzzles are good for mental exercise, especially when you're student. :-) – Parasympathetic

@paxdiablo: honestly i think this is a exercise in bit operations – Antechamber

Is a comparison a conditional? Personally I consider it one, but your instructor might or might not... – Garibull

@Foo Bah: Yes, it involves bitops, but not in the way you're thinking. – Objurgate

Max = (a > b ? a : b) > c ? (a > b ? a : b) : c; – Administer

"But again its restricted to use ternary operator." is not a clear as it could be. It is easy to read as is: "restricted to using the ternary operator" (?: must be used) , when "restricted against using the ternary operator" is meant (?: must not be used) . I'd say simple: "The ternary operator may not be used." – Etui

Answer 1

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

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:

Parasympathetic

Can you provide bit explanation?? – Knout

Hah. That's clever and sneaky. – Thereinafter

@Chirag Fanse: He's taking advantage of short circuiting. – Thereinafter

@Chirag Fanse: Essentially when you have a || operator, the value on the right hand side will not be evaluated if the left hand side is true, as the result will be true regardless. Therefore, in this situation if a > b it won't perform (m = b), likewise for c. – Insignia

@Chirag does the or operator count as conditional? – Antechamber

@Chirag: m = a; if (m <= b) {break;} else {m = b; if (m <= c) {break;} else {m = c;} – Volley

@Foo, no, it's an expression with side effects, not a conditional. Naked expressions like 42; are perfectly valid C statements (although not very useful without side effects). – Kiddy

@Kiddy i was asking whether or not || is considered a conditional as per the terms of the question (hard to imagine ternary counting as conditional but not ||) – Antechamber

for what it's worth, (m<b) && (m=b); is arguably more readable, and saves an assignment when m==b. – Carbolated

@Dave: You can still save the assignment by change m>b with m>=b in my code, though I agree your advice for && is good. :-) – Parasympathetic

This is very simple but very cool! Does assignment in C return an int then ((m=b)) or can any expression be evaluated after the boolean op? I'm unfamiliar with C so just wondering. – Interpellate

Note that this solution does not avoid branching, so while there are no conditional expressions in the C++ code, there are branches in the real code. The && is an implicit if. If the goal of avoiding if or the ternary operator (?:) was to avoid branches which can speedup processing by the CPU, then other solutions are better. – Lib

@David: Other solutions are better in terms of what? "speedup processing by the CPU" Or ...? – Parasympathetic

@Nawaz: avoiding branches, which can in turn speedup processing as when there is a branch misprediction the compiler has to flush part of the processing pipeline and that can be expensive (by a very relative meaning of expensive). Usually when you want to avoid if you do not actually want to avoid typing the two letters, but rather the branch that is inserted into the program by that if. That is, if you care, which in most cases you should not even be thinking on such low level microoptimizations. – Lib

@David: I think, its difficult say which solutions would be faster without experimentation and profiling. Apart from that, are you sure the other solutions including yours do not produce branches in the machine codes , and mine must be producing branches? I would like to see it happens before believing. – Parasympathetic

@Nawaz: None of the other three solutions generates branches, as all of the code is executed in all code paths, while your solution may involve branches. The reason for the may in italics, is that just out of curiosity I implemented the 2 way max in the different flavors, and the compiler removed the branch (I haven't tried with the 3-way max, so I cannot say whether the branch will be removed or not). I have added the assembly output description for the trivial implementations to my answer, if you are curious to know what the generated code looks like. – Lib

I think the spirit of the question would be whether the sample code has any form of logical conditional check. Circumventing that with semantics is just a technicality, and not an accurate representation of the problem. – Slick

@Nawaz: very nice solution. I like it sir. This logic can be reversed & used to find minimum number also. I tried it here ideone.com/kJQCNF. Thank you so much. – Ghostly

Answer 2

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);
}

Antechamber

Answer 3

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 max( int a, int b ) {
   int lookup[] { a, b };
   return lookup[ a < b ];
}

If the expression a<b is correct we return b, carefully stored in the first index of the lookup array. If the expression yields false, then we return a that is stored as element 0 of the lookup array. Using this as a building block, you can say:

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 max using the result already stored in lookup[0] and inlining the original call to 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 here modified to use an inline function rather than a macro. The next option would be either this one or the one by @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 if or the ternary operator ?:, but that they avoid branching altogether, and that can have an impact in performance. The branch-predictor in the CPU cannot possibly miss when there are no branches.

---

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:

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 cmovge instruction (test carried out with g++ in an intel x64 platform):

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 code and let the compiler optimize it for us.

Pham

cmovge is a branch statement. It looks a the result of a previous conditional and takes an action accordingly. It happens to be a pretty good conditional instruction for this, but it's still a branch. – Ezekielezell

@awoodland: I don't think you can call that a branch, the code flow cannot possibly go in two directions. It does take into account the previous value to produce one or other outcome, but it cannot be mispredicted, it will not have to flush the instruction pipeline... It will probably be slower than other instructions (it cannot be reordered, the execution depends on the previous execution, so it cannot be parallelized with it...) but it does not branch, unless I am missing something here. – Lib

Its behaviour depends on the condition register which I would have said was the very definition of a branch. Logically its behaviour looks like a branch - the values in memory can become one of two things after the instruction has completed. If that can be predicted and consequently mis-predicted I'm less sure on for current processor designs. It's not inconceivable that a prediction of the "do nothing" path could be made erroneously and prediction/mis-prediction is not a prerequisite for an instruction being a branch anyway. (I agree it answers the question - it's not a conditional statement) – Ezekielezell

@awoodland: I have a different understanding of what a branch is, but I am no assembler expert. To me is a point in code in which the next instruction (note: not the result of the instruction, but the next instruction) can be one of a set (i.e. a conditional jump), and the associated problem is that the processor instruction pipeline might have to be ditch in the case of a misprediction. In this case, whether the register value is changed or not, the next instruction is always known, and whether the value is updated or not, the instruction pipeline can be used at its best. – Lib

Answer 4

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.

---

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 > b might involve conditional jumps, but they're not visible from C.)

Objurgate

A nice, certainly constant time, answer. – Etui

Maybe salvageable as a * (a >= b & a >= c) | b * (b >= a & b >= c) | c * (c >= a & c >= b);? – Etui

@chux: Interesting. It works for the trivial examples I tried. I'll have to think about it and update later. – Objurgate

Answer 5

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));
}

Interlocution

Answer 6

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.

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;
}

Kathlyn

Answer 7

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;
}

Slick

1) sort (int & a, int & b, int & c) is not a valid C syntax. 2) a-b overflows leading to UB in C, for about half of all a,b combinations. – Etui

@chux From the top of my head I would argue that it is only a fourth of all combinations. Going from 0 (no overflow possible) to MAX_INT(a half of all combinations cause overflow). The result should be in the middle. Same goes for 0 to MIN_INT – Nez

Answer 8

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.

Yggdrasil

Answer 9

#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;
}            

Carniola

Answer 10

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;

Thorium

A (not-unrolled) loop is a conditional statement. – Wingover

Answer 11

#Python program to find the largest among three integer numbers using ternary operators:
x=int(input("enter 1st number: "))
y=int(input("enter second number: "))
z=int(input("enter third number: "))
large=(x if x>z else z ) if x>y else (y if y>z else z)
print(large ,"is the largest number.")

Vibes

The question specifically asks for a solution in C, so why give an answer using Python? – Passionate

Answer 12

int compare(int a,int b, intc)
{
    return (a > b ? (a > c ? a : c) : (b > c ? b : c))
}

Urethra

There's three ternary operators in this one. – Soliloquize

Answer 13

Try this.

#include "stdio.h"
main() {
    int a,b,c,rmvivek,arni,csc; 
    printf("enter the three numbers");
    scanf("%d%d%d",&a,&b,&c);
    printf("the biggest value is %d",(a>b&&a>c?a:b>c?b:c));
}

Rolandrolanda

I know this is an old solution but OP explicitly said no ternary operators. – Karimakarin

Answer 14

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

Diorio

@hari.I tried like this but again, you are using ternary operator which is not allowed... – Knout

That's a ternary by the way, already discounted as a possibility. – Kiddy