¿Cómo puedo devolver mediante programación el máximo de dos enteros sin usar ningún operador de comparación y sin usar if, else, etc?
-
03-07-2019 - |
Pregunta
¿Cómo devuelvo por programación el máximo de dos enteros sin usar operadores de comparación y sin usar si
, else
, etc.?
Solución
max: // Colocará MAX (a, b) en un
a -= b;
a &= (~a) >> 31;
a += b;
Y:
int a, b;
min: // Colocará MIN (a, b) en un
a -= b;
a &= a >> 31;
a += b;
de aquí .
Otros consejos
http://www.graphics.stanford.edu/~seander /bithacks.html#IntegerMinOrMax
r = x - ((x - y) & -(x < y)); // max(x, y)
Puedes divertirte aritméticamente cambiando (x - y)
para saturar el bit de signo, pero esto suele ser suficiente. O puedes probar el bit alto, siempre divertido.
Creo que lo tengo.
int data[2] = {a,b};
int c = a - b;
return data[(int)((c & 0x80000000) >> 31)];
¿Esto no funcionaría? Básicamente, tomas la diferencia de los dos y luego devuelves uno u otro basado en el bit de signo. (Así es como el procesador hace más o menos que de todos modos). Entonces, si el bit de signo es 0, devuelve a, ya que a es mayor o igual que b. Si el bit de signo es 1, devuelva b, porque restar b de a causó que el resultado fuera negativo, lo que indica que b fue mayor que a. Solo asegúrate de que tus ints tengan 32bits firmados.
En el mundo de las matemáticas:
max(a+b) = ( (a+b) + |(a-b)| ) / 2
min(a-b) = ( (a+b) - |(a-b)| ) / 2
Además de ser matemáticamente correcto, no está haciendo suposiciones sobre el tamaño del bit como deben hacer las operaciones de cambio.
| x |
representa el valor absoluto de x.
Comentario:
Tienes razón, el valor absoluto fue olvidado. Esto debería ser válido para todas las a, b positivas o negativas
return (a > b? a: b);
o
int max(int a, int b)
{
int x = (a - b) >> 31;
int y = ~x;
return (y & a) | (x & b);
}
no tan elegante como el anterior ... pero ...
int getMax(int a, int b)
{
for(int i=0; (i<a) || (i<b); i++) { }
return i;
}
Ya que este es un rompecabezas, la solución será un poco complicada:
let greater x y = signum (1+signum (x-y))
let max a b = (greater a b)*a + (greater b a)*b
Esto es Haskell, pero será el mismo en cualquier otro idioma. La gente de C / C # debe usar " sgn " (o " signo " ;?) en lugar de signum.
Tenga en cuenta que esto también funcionará en ints de tamaño arbitrario y en reales.
Del artículo de "Polymorphic Games" de z0mbie's (famoso escritor virii), quizás te resulte útil:
#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))
saludos
Esto es una especie de trampa, usando lenguaje ensamblador, pero es interesante, sin embargo:
// 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));
}
Si desea ser estricto con las reglas y dice que la instrucción cmpl
es ilegal para esto, entonces la siguiente secuencia (menos eficiente) funcionará:
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");
}
int max(int a, int b)
{
return ((a - b) >> 31) ? b : a;
}