Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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.

share|improve this question
    
What about defining an extra function? If this is allowed, how many tokens does it count as? –  voidpigeon Jun 25 at 0:16
    
@voidpigeon You are only allowed to have one function, the one that takes the 3 inputs and outputs. –  qwr Jun 25 at 0:20
1  
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 at 0:36
    
@primo I specifically asked for 3 inputs because it actually allows for some interesting improvements –  qwr Jun 25 at 0:39
2  
Can we use inbuilt functions? –  Registered User Jun 25 at 4:44

16 Answers 16

up vote 7 down vote accepted

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));
}
share|improve this answer
1  
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 at 0:48

Javascript

6 tokens

function maxOf3(a, b, c) {
    (b>a) && (a=b);
    (c>a) && (a=c);
    return a;
}
share|improve this answer
5  
+1 I see shortcut evaluation as a type of branching, but it's not forbidden in the rules –  edc65 Jun 25 at 1:33
10  
I would consider this as branching, haha –  justhalf Jun 25 at 2:52
2  
@edc65 It is. Allowing && and || was likely an oversight, which should be pointed out, rather than exploited. –  primo Jun 25 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 at 5:54
2  
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 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. :-)

share|improve this answer
2  
This is a creative answer, but _mm_max_epi32 is not one of the allowed operations... –  Riot Jun 25 at 14:03
1  
@Riot However strictly we are not even allowed to return or output according to the allowed operation list... –  Vality Jun 25 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 at 14:34
1  
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 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.

share|improve this answer

Javascript 12

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

Via bit twiddling hacks.

JSFiddle with a few tests cases.

share|improve this answer

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));
}
share|improve this answer
1  
You are not allowed to create new functions –  qwr Jun 25 at 1:16
    
:( 14 tokens then –  Fabricio Jun 25 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 :)

share|improve this answer
    
You are not allowed to create new functions –  qwr Jun 25 at 9:28
    
Ahh ok! Didn't read the comments :) –  Mardoxx Jun 25 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 at 14:40
1  
@Cruncher I edited the answer I did max2(max2(x,y),z) initially :) –  Mardoxx Jun 25 at 15:02
    
@Mardoxx ah. Well +1 –  Cruncher Jun 25 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;
}
share|improve this answer
    
Fail for big numbers (>2^30), see comment codegolf.stackexchange.com/questions/32476/#comment68870_32477 –  edc65 Jun 25 at 21:08
    
Looks fine to me: ideone.com/pEsvG3 –  Riot Jun 26 at 8:06
    
Did you atctually read the comment? I think 2billions is greater than 0 [ideone.com/vlcnq9 ] –  edc65 Jun 26 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 at 22:00
    
It's not the 0 involved. The problem are big numbers and overflow, try max(2000000000, -200000000, 1111111111). –  edc65 Jun 26 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.

share|improve this answer
    
It is branching, only inline. Specifically, the ubiquitous ternary operator (which this essentially is) is not one of the allowed operations. –  tomsmeding Jun 25 at 18:04
    
Thanks @tomsmeding, may I ask what is the ubiquitous ternary operator (is it IIF() in my code?) –  Alex Jun 25 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 at 18:57
    
thank you! I will try come up with a better answer –  Alex Jun 25 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)
share|improve this answer

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

}

share|improve this answer
    
Please write actual code, and provide the count of tokens in your answer. –  ProgramFOX Jun 25 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];
}
share|improve this answer

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

share|improve this answer

R (10 tokens)

function max(a, b, c) {
  max <- a
  max <- max + (b - max) * (b > max)
  max <- max + (c - max) * (c > max)
  return(max)
}
share|improve this answer

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

share|improve this answer
    
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 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 at 16:00

Brainfuck (Not competing)

>,[-<+>>>+<<]>,[-<+>>>+<<]>[>[-<->>]<<]<[-]>[-]>[-]<<<[->>>>+<<<<]>>>>[-<+>>>+<<]>,[-<+>>>+<<]>[>[-<->>]<<]<<
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.