How do I programmatically return the max of two in

问题:

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

回答1:

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.

回答2:

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.

回答3:

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.

回答4:

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

回答5:

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

回答6:

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

int getMax(int a, int b)
{
    for(int i=0; (i<a) || (i<b); i++) { }
    return i;
}

回答7:

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.

回答8:

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

回答9:

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

回答10:

int max(int a, int b)
{
   return ((a - b) >> 31) ? b : a;
}