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?

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:

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

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.

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.)

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

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

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

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.

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

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;

Answer 11

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

Answer 12

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

Answer 13

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