Find the maximum of 3 numbers without branching

Question

This time around your goal is to find the maximum of 3 integers (from -(2^31) to 2^31 - 1 in binary 2's complement) without using branching or loops.

You are only allowed to use

• Inequality/Equality (==, >, >=, <, <=, !=) These count as 2 tokens.

• Arithmetic (+, -, *, /)

• Logical Operators (! not, && and, || or)

• Bitwise Operators (~ not, & and, | or, ^ xor, <<, >>, >>> arithmetic and logical left and right shifts)

• Constants. 0 tokens

• Variable assignment. 0 tokens

Input 3 variables as a, b and c. Output the maximum number.

Standard atomic code-golf rules apply. If you have any questions please leave them in the comments. One token is any of the above with the special rules.

Answer 1

Javascript 10 tokens

Edit Using < and * instead of bit fiddling - as pointed out in comments, bits operations may fail for input near the range limit (over 30 bits)

function Max(x,y,z)
{
  var d=y-x;
  x=y-d*(d<0);
  d=x-z;
  return x-d*(d<0);
}

C 8 tokens

Language agnostic in fact, any C like language will do. To be picky, in standard C it's not portable because right shift may not extend the sign (but in common implementations it does).

In C (and C++, C#, and Java I think) we can easily handle overflow problems using bigger temporary values:

int Max(int x, int y, int z)
{
    long long X = x;
    long long Y = y;
    long long Z = z;
    long long D = Y-X;
    X=Y-((D>>63)&D);
    D=X-Z;
    return (int) (X-((D>>63)&D));
}

Answer 2

Javascript

6 tokens

function maxOf3(a, b, c) {
    (b>a) && (a=b);
    (c>a) && (a=c);
    return a;
}

Answer 3

C: 10 tokens

int max(int a, int b, int c)
{
    a += (b > a) * (b - a);
    a += (c > a) * (c - a);
    return a;
}

Inspired by @openorclose's answer, but converted to C and made branchless using multiplication rather than short circuit boolean operators.

Answer 4

Javascript

14 tokens

function max (a, b, c)
{
    var ab = (a >= b) * a + (a < b) * b;
    return (ab >= c) * ab + (ab < c) * c;
}

Answer 5

Many languages (Python) (10 tokens)

def max3(x,y,z):
    m = x ^ ((x ^ y) & -(x < y))
    return m ^ ((m ^ z) & -(m < z))

print max3(-1,-2,-3) # -1
print max3(-1,2,10) # 10

https://graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax

Oh, someone already posted it :)

Answer 6

C++11: 15 tokens

Using only arithmetic and bitwise operators (since equality and boolean logic operators make it too easy)...

#include <iostream>

auto max(int32_t a, int32_t b, int32_t c)->int32_t {
  return c - ((c - (a - ((a - b) & (a - b) >> 31))) & (c - (a - ((a - b) & (a - b) >> 31))) >> 31);
}

auto main()->int {
  // test harness
  std::cout << max(9, 38, 7) << std::endl;
  return EXIT_SUCCESS;
}

Answer 7

TIS-100, 8 operations

MOV ACC UP #A
SUB UP     #B
SUB 999
ADD 999
ADD UP     #B
SUB UP     #C
SUB 999
ADD 999
ADD UP     #C
MOV ACC DOWN

The provider(UP) only do MOVs so not shown in the code Maybe not work when too near the 999 edge

Answer 8

J (Not competing)

I was just wondering what the a solution in J would look like. This uses a , and a # though, so it won't be competing.

((a<b),(b<c),(c<a))#b,c,a

This would compete, but is way too long, with 9 tokens:

(b*a<:b)+(c*b<c)+(a*c<a)

Answer 9

we have the following assumptions:

• max(a;b)=(a+b + |a-b|)/2

• max(a;b;c)=max(max(a;b);c)

• abs(a)=(a + (a >> 31)) ^ (a >> 31)

we can use the pseudo-code:

function max(a,b,c)

{

out1=( (a+b) + (( (a-b) + ((a-b) >> 31)) ^ ((a-b)>> 31))) div 2

out2=( (out1+c) + (( (out1-c) + ((out1-c) >> 31)) ^ ((out1-c)>> 31))) div 2

return out2

}

Answer 10

C# (2nd try)

I got it... No integrated functions...

But is it allowed to use other integrated datatypes or just plain int? If allowed I would propose:

int foo2(int a, int b, int c)
{
   var x = new SortedList<int,int>();

   x[a] = 1;
   x[b] = 1;
   x[c] = 1;

   return x.Keys[2];
}

Answer 11

javascript 8 tokens

although similar to @openorclose's answer, i do actually use the logical operators for the assignment itself.

function max( a, b, c ) {
    x=( a > b && a) || b;
    return ( x > c && x ) || c;
}

fiddle

Answer 12

R (10 tokens)

function max(a, b, c) {
  max <- a
  max <- max + (b - max) * (b > max)
  max <- max + (c - max) * (c > max)
  return(max)
}

Answer 13

Brainfuck (Not competing)

>,[-<+>>>+<<]>,[-<+>>>+<<]>[>[-<->>]<<]<[-]>[-]>[-]<<<[->>>>+<<<<]>>>>[-<+>>>+<<]>,[-<+>>>+<<]>[>[-<->>]<<]<<

Answer 14

VBA (6 tokens)

 Function max3(a As Integer, b As Integer, c As Integer)
 i = IIf(a >= b And a >= c, a, IIf(b >= c, b, c))
 max3 = i
 End Function  

not sure if this is not branching.

Answer 15

JavaScript: 4 tokens (** based on broad interpretation of "assignment"!)

Obviously my score of 4 is extremely generous/lenient!

To arrive at that score I've assumed "assignment" (worth 0 tokens in the question) includes such things as additive assignment, subtractive assignment, multiplicative assignment, and XOR-ing (^=) assignment

function f(a, b, c) {
  d = a;
  d -= b;
  d = d >= 0;

  a *= d;  //a = a if (a>=b), else 0
  d ^= true; //invert d
  b *= d;  //b = b if (b<a), else 0

  a += b;  //a is now max(a,b)

  d = a;
  d -= c;
  d = d >= 0;

  a *= d;  //a = a if (a>=c), else 0
  d ^= true; //invert d
  c *= d;  //c = c if (c<a), else 0
  a += c;  //a is now max(max(a,b),c)

  return a;
}

If those assignments actually count the score is 14 :)