17

How do I programmatically return the maximum of two integers without using any comparison operators and without using if, else, etc?

15
  • 5
    -1: Why no comparisons? Seems like an artificial question to me.
    – Alex Lyman
    Oct 22, 2008 at 20:28
  • 17
    Why do these bizarre puzzles show up as interview questions? Do mechanics get asked things like how they would get a gasoline engine to run without spark plugs? Oct 22, 2008 at 20:41
  • 1
    Maybe the idea is that the candidate scores maximum points by asking why on earth anyone would care to know the answer :-) It would make sense for an assembly programming or compiler writing job, but it's something you never need to do in C. The compiler writer will have optimised (a<b)?b:a for you. Oct 22, 2008 at 21:04
  • 1
    @Mark: the reason I say appropriate for assembler programmers is just that tricks to avoid jumps are pretty standard fare (unless your CPU optimises microcode really well). On ARM for instance clearly you would use conditionals, so the question would be "how to do this without a branch". Maybe. Oct 23, 2008 at 3:31
  • 4
    @Michael Burr: at least one mechanic got asked how to get a gasoline engine to run without spark plugs. His name was "Diesel". Mar 29, 2010 at 12:01

12 Answers 12

29

max: // Will put MAX(a,b) into a

a -= b;
a &= (~a) >> 31;
a += b;

And:

int a, b;

min: // Will put MIN(a,b) into a

a -= b;
a &= a >> 31;
a += b;

from here.

5
  • 1
    what about 64-bit ints or arbitrary-sized ints? :)
    – ADEpt
    Oct 22, 2008 at 20:51
  • 1
    Vote down for that? Embed it in a templated or polymorphic inline function - exercise left for the astute reader.
    – plinth
    Oct 22, 2008 at 20:54
  • By definition polymorphic functions can't be inline. You need to evaluate the function call by vtable at runtime. But neat solution, doesn't work for unsigned ints though... Oct 22, 2008 at 21:27
  • 1
    You should mention this depends on signed right shifts preserving sign. This is not guaranteed by the C standard afaik. However it does work under gcc for me.
    – freespace
    Oct 23, 2008 at 2:22
  • @VinayakGarg - if a == b then the value of a is zero until the last step, at which point it is added to b. It works.
    – hoodaticus
    Dec 15, 2016 at 19:49
8

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

r = x - ((x - y) & -(x < y)); // max(x, y)

You can have fun with arithmetically shifting (x - y) to saturate the sign bit, but this is usually enough. Or you can test the high bit, always fun.

1
  • 4
    Well, to be perfectly pedantic, you should be talking about branches, not comparison operators, since branches are far more likely to cause performance issues. But anyways, that's why I added the additional commentary below, since x < y is equivalent to getting the high bit of x - y.
    – MSN
    Oct 22, 2008 at 20:54
7

In the math world:

max(a+b) = ( (a+b) + |(a-b)| ) / 2
min(a-b) = ( (a+b) - |(a-b)| ) / 2

Apart from being mathematically correct it is not making assumptions about the bit size as shifting operations need to do.

|x| stands for the absolute value of x.

Comment:

You are right, the absolute value was forgotten. This should be valid for all a, b positive or negative

3
  • This does not seem to be correct. For example: min(-500, 0)=((-500+0)-(-500-0))/2=(-500+500)/2=0
    – Sander
    May 15, 2009 at 8:54
  • 2
    Aren't you just hiding the comparison here? Since abs(x) := x >= 0 ? x : -x. So you will need a branching operator just the same. Of course you can prevent branching by using an &-mask, but then you'd have to make assumptions on the bit count of the operands.. Dec 12, 2014 at 1:02
  • 1
    "should be valid for all a,b positive or negative" does not apply to int as a+b can readily overflow. Aug 30, 2015 at 20:18
6

I think I've got it.

int data[2] = {a,b};
int c = a - b;
return data[(int)((c & 0x80000000) >> 31)];

Would this not work? Basically, you take the difference of the two, and then return one or the other based on the sign bit. (This is how the processor does greater than or less than anyway.) So if the sign bit is 0, return a, since a is greater than or equal to b. If the sign bit is 1, return b, because subtracting b from a caused the result to go negative, indicating that b was greater than a. Just make sure that your ints are 32bits signed.

7
  • I don't understand what the data array is for. Oct 22, 2008 at 20:44
  • I think you meant to use the return line as an index into the data array.
    – Bill K
    Oct 22, 2008 at 20:46
  • In case if you want the above code to work in Java, You may need to substitute ">>" with ">>>" .Using ">>" operator will result in negative index where a and b have negative values especially if a < b. For example, try a=-4 and b =-3
    – BlueGene
    Oct 27, 2008 at 23:24
  • 1
    Its C code. Anyway, if you wanted it to be really "complete" in C, you need to substitute 31 with "(sizeof(int) * 8 - 1)", which will work regardless of the architecture. Usually though, I work on a 32bit architecture, so I'm used to assuming a size of 32 bits.
    – Blank
    Oct 29, 2008 at 18:59
  • @Nicholas: make that (sizeof(int) * CHAR_BIT - 1). Make sure you #include <limits.h>.
    – pmg
    Nov 7, 2009 at 16:02
3

return (a > b ? a : b);

or

int max(int a, int b)
{
        int x = (a - b) >> 31;
        int y = ~x;
        return (y & a) | (x & b); 
}
3
  • I think > is not allowed. Also ?: is too much like if-else.
    – MrDatabase
    Oct 22, 2008 at 20:22
  • Bobs answer is a reasonable practical solution to the question without an if/else.
    – EvilTeach
    Oct 22, 2008 at 20:28
  • @EvilTeach: the ?: op implies an comparison when compiled, which is not what the OP wanted.
    – Calyth
    Jan 12, 2009 at 21:48
3

From z0mbie's (famous virii writer) article "Polymorphic Games", maybe you'll find it useful:

#define H0(x)       (((signed)(x)) >> (sizeof((signed)(x))*8-1))
#define H1(a,b)     H0((a)-(b))

#define MIN1(a,b)   ((a)+(H1(b,a) & ((b)-(a))))
#define MIN2(a,b)   ((a)-(H1(b,a) & ((a)-(b))))
#define MIN3(a,b)   ((b)-(H1(a,b) & ((b)-(a))))
#define MIN4(a,b)   ((b)+(H1(a,b) & ((a)-(b))))
//#define MIN5(a,b)   ((a)<(b)?(a):(b))
//#define MIN6(a,b)   ((a)>(b)?(b):(a))
//#define MIN7(a,b)   ((b)>(a)?(a):(b))
//#define MIN8(a,b)   ((b)<(a)?(b):(a))

#define MAX1(a,b)   ((a)+(H1(a,b) & ((b)-(a))))
#define MAX2(a,b)   ((a)-(H1(a,b) & ((a)-(b))))
#define MAX3(a,b)   ((b)-(H1(b,a) & ((b)-(a))))
#define MAX4(a,b)   ((b)+(H1(b,a) & ((a)-(b))))
//#define MAX5(a,b)   ((a)<(b)?(b):(a))
//#define MAX6(a,b)   ((a)>(b)?(a):(b))
//#define MAX7(a,b)   ((b)>(a)?(b):(a))
//#define MAX8(a,b)   ((b)<(a)?(a):(b))

#define ABS1(a)     (((a)^H0(a))-H0(a))
//#define ABS2(a)     ((a)>0?(a):-(a))
//#define ABS3(a)     ((a)>=0?(a):-(a))
//#define ABS4(a)     ((a)<0?-(a):(a))
//#define ABS5(a)     ((a)<=0?-(a):(a))

cheers

2

not as snazzy as the above... but...

int getMax(int a, int b)
{
    for(int i=0; (i<a) || (i<b); i++) { }
    return i;
}
2
  • oops, no comparison ops! doh! :)
    – mspmsp
    Oct 22, 2008 at 20:35
  • I also wonder if the 'for" might be construed as being like "if, else, etc." Oct 22, 2008 at 20:37
2

Since this is a puzzle, solution will be slightly convoluted:

let greater x y = signum (1+signum (x-y))

let max a b = (greater a b)*a + (greater b a)*b

This is Haskell, but it will be the same in any other language. C/C# folks should use "sgn" (or "sign"?) instead of signum.

Note that this will work on ints of arbitrary size and on reals as well.

1

This is kind of cheating, using assembly language, but it's interesting nonetheless:


// GCC inline assembly
int max(int a, int b)
{
  __asm__("movl %0, %%eax\n\t"   // %eax = a
          "cmpl %%eax, %1\n\t"   // compare a to b
          "cmovg %1, %%eax"      // %eax = b if b>a
         :: "r"(a), "r"(b));
}

If you want to be strict about the rules and say that the cmpl instruction is illegal for this, then the following (less efficient) sequence will work:


int max(int a, int b)
{
  __asm__("movl %0, %%eax\n\t"
      "subl %1, %%eax\n\t"
          "cmovge %0, %%eax\n\t"
          "cmovl %1, %%eax"
         :: "r"(a), "r"(b)
         :"%eax");
}
1
  • 2
    He said no if, meaning no coparison and cmpl is just that, a comparison.
    – Mecki
    Oct 22, 2008 at 21:08
1

These functions use comparisons but no tests and are fully defined on Standard compliant systems:

int min(int a, int b) {
    return (a <= b) * a + (b < a) * b;
}
int max(int a, int b) {
    return (a <= b) * b + (b < a) * a;
}

Here is an alternative without multiplications, portable to systems that use two's complement for negative numbers:

int min(int a, int b) {
    return (a & -(a <= b)) | (b & -(b < a));
}
int max(int a, int b) {
    return (b & -(a <= b)) | (a & -(b < a));
}

Both versions work for all integer types.

Note that both gcc and clang generate branchless code for the above functions, and clang generates the same optimal code for both alternatives as can be seen on this Godbolt Compiler Explorer session.

0

This is my implementation on C# using only +, -, *, %, / operators

using static System.Console;

int Max(int a, int b) => (a + b + Abs(a - b)) / 2;
int Abs(int x) => x * ((2 * x + 1) % 2);

WriteLine(Max(-100, -2) == -2); // true
WriteLine(Max(2, -100) == 2);   // true
2
  • (2 * x + 1) overflows for about half of the range of type int. a - b exceeds the range of int quite easily too.
    – chqrlie
    Feb 2, 2021 at 22:11
  • @chqrlie Yes, you right. This code not for production use, it's for educational purpose Feb 3, 2021 at 12:49
-2
int max(int a, int b)
{
   return ((a - b) >> 31) ? b : a;
}
1
  • 1
    right shift isn't necessarily an arithmetic (sign-extended) shift
    – phuclv
    Sep 30, 2017 at 5:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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