# Find the maximum of 3 numbers without branching

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.

• What about defining an extra function? If this is allowed, how many tokens does it count as? Jun 25, 2014 at 0:16
• @voidpigeon You are only allowed to have one function, the one that takes the 3 inputs and outputs.
– qwr
Jun 25, 2014 at 0:20
• At first glance I thought, "we've had this before.", but I think comparators costing 2 changes the game quite a bit. Jun 25, 2014 at 0:36
• @primo I specifically asked for 3 inputs because it actually allows for some interesting improvements
– qwr
Jun 25, 2014 at 0:39
• Can we use inbuilt functions? Jun 25, 2014 at 4:44

# Javascript

6 tokens

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

• +1 I see shortcut evaluation as a type of branching, but it's not forbidden in the rules Jun 25, 2014 at 1:33
• I would consider this as branching, haha Jun 25, 2014 at 2:52
• @edc65 It is. Allowing && and || was likely an oversight, which should be pointed out, rather than exploited. Jun 25, 2014 at 5:09
• @primo This was an interesting issue. I believe some CISC architectures have instructions that include conditional statements, so I'm not sure how those would be counted.
– qwr
Jun 25, 2014 at 5:54
• I guess it should be 4 tokens i.e 2 &&, < and >. The = is used as an assignment and counts as 0 Jun 25, 2014 at 12:40

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

• I'm being picky, but using C ints your code doesn't work for x=2147483647, y = -2, z=0. Your choice if you want to change it
– qwr
Jun 25, 2014 at 0:48

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

# Javascript

14 tokens

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

• You are not allowed to create new functions
– qwr
Jun 25, 2014 at 1:16
• :( 14 tokens then Jun 25, 2014 at 1:17

## 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 :)

• You are not allowed to create new functions
– qwr
Jun 25, 2014 at 9:28
• Ahh ok! Didn't read the comments :) Jun 25, 2014 at 10:24
• @qwr I don't get it, you said: You are only allowed to have one function, the one that takes the 3 inputs and outputs. That's exactly what this answer has. The 2 prints are just test cases Jun 25, 2014 at 14:40
• @Cruncher I edited the answer I did max2(max2(x,y),z) initially :) Jun 25, 2014 at 15:02
• @Mardoxx ah. Well +1 Jun 25, 2014 at 15:57

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

• Fail for big numbers (>2^30), see comment codegolf.stackexchange.com/questions/32476/#comment68870_32477 Jun 25, 2014 at 21:08
• Looks fine to me: ideone.com/pEsvG3
– Riot
Jun 26, 2014 at 8:06
• Did you atctually read the comment? I think 2billions is greater than 0 [ideone.com/vlcnq9 ] Jun 26, 2014 at 8:19
• Ah i see; yes it does have a problem with those numbers in your other comment, when a 0 is involved. But not for 2^30 as you said. ideone.com/LicmXa
– Riot
Jun 26, 2014 at 22:00
• It's not the 0 involved. The problem are big numbers and overflow, try max(2000000000, -200000000, 1111111111). Jun 26, 2014 at 22:07

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


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

}

• Please write actual code, and provide the count of tokens in your answer. Jun 25, 2014 at 18:20

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


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

## R (10 tokens)

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


## Brainfuck (Not competing)

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


# TIS-100, 8 operations

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


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

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.

• It is branching, only inline. Specifically, the ubiquitous ternary operator (which this essentially is) is not one of the allowed operations. Jun 25, 2014 at 18:04
• Thanks @tomsmeding, may I ask what is the ubiquitous ternary operator (is it IIF() in my code?)
– Alex
Jun 25, 2014 at 18:55
• yes sorry, with ubiquitous I meant that it's present in pretty much every language, and the ternary operator is your IIf, Inline-If. In most languages, it is, for example, a>=b ? a : b. It is branching indeed. Jun 25, 2014 at 18:57

## 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 :)

• Because d -= b is actually the same as d = d - b, I would say that you use arithmetic and that you should count this as a token. Jun 26, 2014 at 14:27
• Yes, I realise that - I was (jokingly) trying to take advantage of the meaning of "assignment". I think I made that fairly obvious! Jun 26, 2014 at 16:00