# 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? – afuous Jun 25 '14 at 0:16
@voidpigeon You are only allowed to have one function, the one that takes the 3 inputs and outputs. – qwr Jun 25 '14 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. – primo Jun 25 '14 at 0:36
@primo I specifically asked for 3 inputs because it actually allows for some interesting improvements – qwr Jun 25 '14 at 0:39
Can we use inbuilt functions? – Registered User Jun 25 '14 at 4:44

# 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 `int`s your code doesn't work for x=2147483647, y = -2, z=0. Your choice if you want to change it – qwr Jun 25 '14 at 0:48

# 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 – edc65 Jun 25 '14 at 1:33
I would consider this as branching, haha – justhalf Jun 25 '14 at 2:52
@edc65 It is. Allowing `&&` and `||` was likely an oversight, which should be pointed out, rather than exploited. – primo Jun 25 '14 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 '14 at 5:54
I guess it should be 4 tokens i.e 2 `&&`, `<` and `>`. The `=` is used as an assignment and counts as 0 – Clyde Lobo Jun 25 '14 at 12:40

## C/C++ with SSE intrinsics (0 tokens)

Because everything's better with SIMD...

``````int foo(int32_t a, int32_t b, int32_t c)
{
__m128i va = _mm_set1_epi32(a);
__m128i vb = _mm_set1_epi32(b);
__m128i vc = _mm_set1_epi32(c);
__m128i vmax = _mm_max_epi32(va, _mm_max_epi32(vb, vc));
return _mm_cvtsi128_si32(vmax);
}
``````

Before anyone comments, yes I know this probably isn't within the spirit of the challenge, I just added it as a "fun" entry. :-)

-
This is a creative answer, but _mm_max_epi32 is not one of the allowed operations... – Riot Jun 25 '14 at 14:03
@Riot However strictly we are not even allowed to return or output according to the allowed operation list... – Vality Jun 25 '14 at 14:10
@Riot: I'm not sure intrinsics count as "operations" - they typically just map to a single machine instruction - but it's moot really - this answer isn't really intended to be a "serious" contender. – Paul R Jun 25 '14 at 14:34
well, that presupposes that executing a machine instruction does not count as performing an operation; however, in your favour, the question also allows some operations that would compile to branching instructions (at least on some architectures with some compilers) anyway, so the boundary between allowed and not allowed is a bit hazy here. – Riot Jun 25 '14 at 14:47

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

``````function max(a,b,c)
{
var m2 = a ^ ((a ^ b) & -(a < b));
return m2 ^ ((m2 ^ c) & -(m2 < c))
}
``````

JSFiddle with a few tests cases.

-

# Javascript

14 tokens

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

6 tokens

``````function max (a, b, c)
{
var ge  = function(a, b) { return a >=b }
var lt  = function(a, b) { return a < b }
var mul = function(a, b) { return a * b }
var add = function(a, b) { return a + b }
var ab = add(mul(ge(a, b), a), mul(lt(a, b), b));
return add(mul(ge(ab, c), ab), mul(lt(ab, c), c));
}
``````
-
You are not allowed to create new functions – qwr Jun 25 '14 at 1:16
:( 14 tokens then – Fabricio Jun 25 '14 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 '14 at 9:28
Ahh ok! Didn't read the comments :) – Mardoxx Jun 25 '14 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 – Cruncher Jun 25 '14 at 14:40
@Cruncher I edited the answer I did `max2(max2(x,y),z)` initially :) – Mardoxx Jun 25 '14 at 15:02
@Mardoxx ah. Well +1 – Cruncher Jun 25 '14 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 – edc65 Jun 25 '14 at 21:08
Looks fine to me: ideone.com/pEsvG3 – Riot Jun 26 '14 at 8:06
Did you atctually read the comment? I think 2billions is greater than 0 [ideone.com/vlcnq9 ] – edc65 Jun 26 '14 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 '14 at 22:00
It's not the 0 involved. The problem are big numbers and overflow, try max(2000000000, -200000000, 1111111111). – edc65 Jun 26 '14 at 22:07

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. – tomsmeding Jun 25 '14 at 18:04
Thanks @tomsmeding, may I ask what is the ubiquitous ternary operator (is it IIF() in my code?) – Alex Jun 25 '14 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. – tomsmeding Jun 25 '14 at 18:57
thank you! I will try come up with a better answer – Alex Jun 25 '14 at 19:00

# 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. – ProgramFOX Jun 25 '14 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[2];
}
``````
-

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

## 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. – ProgramFOX Jun 26 '14 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! – jcdude Jun 26 '14 at 16:00

## Brainfuck (Not competing)

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