Encuentre un máximo de tres números en C sin usar una declaración condicional y un operador ternario

11 minutos de lectura

avatar de usuario
Desarrollador de Microsoft

Tengo que encontrar un máximo de tres números proporcionados por el usuario, pero con algunas restricciones. No está permitido usar ninguna declaración condicional. Intenté usar el operador ternario como se muestra a continuación.

max=(a>b?a:b)>c?(a>b?a:b):c

Pero nuevamente está restringido al uso del operador ternario. ¿Ahora no tengo idea de cómo hacer esto?

  • Esto definitivamente cae en la categoría de “poco probable que ayude a alguien en el futuro” (a menos que sean estudiantes de un educador incompetente). Utilizar las herramientas que tiene, este tipo de pregunta indica que su curso es probablemente una pérdida de tiempo.

    – pax diablo

    16 de agosto de 2011 a las 5:42

  • @paxdiablo. No es una pérdida de tiempo. Más bien es un buen desafío. Hay algunas formas posibles, pero restringidas, así que desafía a encontrar nuevas formas.

    – Desarrollador de Microsoft

    16 de agosto de 2011 a las 5:50

  • @Chirag, un desafío sin resultado útil es un desafío inútil. ¿En qué pieza de código del mundo real usarías una bestia así? Sería alquitranado y emplumado en una revisión de código. John, si quieres enseñarle a alguien sobre operaciones de cortocircuito, hay mejores formas que usar acertijos dudosos.

    – pax diablo

    16 de agosto de 2011 a las 6:03


  • @paxdiablo: Estos acertijos son buenos para el ejercicio mental, especialmente cuando eres estudiante. 🙂

    – Nawaz

    16 de agosto de 2011 a las 6:04

  • @paxdiablo: sinceramente, creo que esto es un ejercicio de operaciones de bits

    – Foo Bah

    16 de agosto de 2011 a las 6:08

avatar de usuario
Nawaz

Aprovechando el cortocircuito en expresiones booleanas:

int max(int a, int b, int c)
{
     int m = a;
     (m < b) && (m = b); //these are not conditional statements.
     (m < c) && (m = c); //these are just boolean expressions.
     return m;
}

Explicación:

en booleano AND operación como x && yy se evalúa si y solo si x es verdad. Si x es falso, entonces y no se evalúa, porque toda la expresión sería falsa, lo que se puede deducir sin siquiera evaluar y. Esto se denomina cortocircuito cuando el valor de una expresión booleana se puede deducir sin evaluar todos los operandos en ella.

Aplique este principio al código anterior. Inicialmente m es a. Ahora si (m < b) es cierto, entonces eso significa, b es mayor que m (que en realidad es a), por lo que la segunda subexpresión (m = b) se evalúa y m se establece en b. Si acaso (m < b) es falso, entonces la segunda subexpresión no será evaluada y m permanecerá a (que es mayor que b). De manera similar, se evalúa la segunda expresión (en la siguiente línea).

En resumen, se puede leer la expresión (m < x) && (m = x) de la siguiente manera: establecer m para x si y solo si m es menos que x es decir (m < x) es verdad. Espero que esto te ayude a entender el código.

Código de prueba:

int main() {
        printf("%d\n", max(1,2,3));
        printf("%d\n", max(2,3,1));
        printf("%d\n", max(3,1,2));
        return 0;
}

Producción:

3
3
3

Nótese la implementación de max da advertencias porque no se utilizan expresiones evaluadas:

prog.c:6: advertencia: el valor calculado no se utiliza
prog.c:7: advertencia: el valor calculado no se utiliza

Para evitar estas advertencias (inofensivas), puede implementar max como:

int max(int a, int b, int c)
{
     int m = a;
     (void)((m < b) && (m = b)); //these are not conditional statements.
     (void)((m < c) && (m = c)); //these are just boolean expressions.
     return m;
}

El truco es que ahora estamos convirtiendo las expresiones booleanas en voidlo que provoca la supresión de las advertencias:

  • ¿Puedes dar una pequeña explicación?

    – Desarrollador de Microsoft

    16 de agosto de 2011 a las 5:46

  • Ja. Eso es inteligente y astuto.

    – GWW

    16 de agosto de 2011 a las 5:46

  • @Chirag Fanse: Se está aprovechando del cortocircuito.

    – GWW

    16 de agosto de 2011 a las 5:47

  • Tenga en cuenta que esta solución no evita derivación, por lo que, si bien no hay expresiones condicionales en el código C++, hay ramas en el código real. los && es un implícito if. Si el objetivo de evitar if o el operador ternario (?:) era para evitar bifurcaciones que pueden acelerar el procesamiento por parte de la CPU, entonces otras soluciones son mejores.

    – David Rodríguez – dribeas

    25 de agosto de 2011 a las 7:53

  • @Nawaz: evitar las bifurcaciones, lo que a su vez puede acelerar el procesamiento, ya que cuando hay una predicción errónea de la bifurcación, el compilador tiene que vaciar parte de la canalización de procesamiento y eso puede ser caro (por un significado muy relativo de caro). Por lo general, cuando desea evitar if en realidad, no desea evitar escribir las dos letras, sino la rama que se inserta en el programa mediante ese si. Es decir, si le importa, que en la mayoría de los casos ni siquiera debería estar pensando en microoptimizaciones de tan bajo nivel.

    – David Rodríguez – dribeas

    25 de agosto de 2011 a las 8:38


Suponiendo que se trata de números enteros, ¿qué tal:

#define max(x,y) (x ^ ((x ^ y) & -(x < y)))
int max3(int x, int y, int z) {
    return max(max(x,y),z);
}

avatar de usuario
David Rodríguez – Dribeas

Solo para agregar otra alternativa para evitar la ejecución condicional (que no es la que usaría, pero parecía faltar en el conjunto de soluciones):

int max( int a, int b, int c ) {
   int l1[] = { a, b };
   int l2[] = { l1[ a<b ], c };
   return l2[ l2[0] < c ];
}

El enfoque utiliza (como la mayoría de los demás), el hecho de que el resultado de una expresión booleana cuando se convierte a int produce 0 o 1. La versión simplificada para dos valores sería:

int max( int a, int b ) {
   int lookup[] { a, b };
   return lookup[ a < b ];
}

Si la expresión a<b es correcto volvemos b, almacenado cuidadosamente en el primer índice de la matriz de búsqueda. Si la expresión da falso, entonces devolvemos a que se almacena como elemento 0 de la matriz de búsqueda. Usando esto como un bloque de construcción, puede decir:

int max( int a, int b, int c ) {
   int lookup[ max(a,b), c ];
   return lookup[ max(a,b) < c ];
}

Que se puede transformar trivialmente al código anterior evitando la segunda llamada al interior max utilizando el resultado ya almacenado en lookup[0] y subrayando la llamada original a max(int,int).


(Esta parte es solo otra prueba de que debe medir antes de saltar a conclusiones, vea la edición al final)

En cuanto a cuál usaría realmente… bueno, probablemente el de @Foo Baa aquí modificado para usar una función en línea en lugar de una macro. La siguiente opción sería esta o la de @MSN aquí.

El denominador común de estas tres soluciones que no está presente en la respuesta aceptada es que no solo evitan la construcción sintáctica de if o el operador ternario ?:pero que evitan derivación en conjunto, y eso puede tener un impacto en el rendimiento. los predictor de rama en la CPU no puede fallar cuando no hay ramas.


Al considerar el rendimiento, primero mida y luego piense

De hecho, implementé algunas de las diferentes opciones para un máximo de 2 vías y analicé el código generado por el compilador. Las tres soluciones siguientes generan el mismo código ensamblador:

int max( int a, int b ) { if ( a < b ) return b; else return a; }
int max( int a, int b ) { return (a < b? b : a ); }
int max( int a, int b ) {
   (void)((a < b) && (a = b));
   return a;
}

Lo cual no es sorprendente, ya que los tres representan exactamente la misma operación. El dato interesante es que el código generado no contiene ninguna rama. La implementación es sencilla con el cmovge instrucción (prueba realizada con g++ en una plataforma intel x64):

movl    %edi, %eax       # move a into the return value
cmpl    %edi, %esi       # compare a and b
cmovge  %esi, %eax       # if (b>a), move b into the return value
ret

El truco está en la instrucción de movimiento condicional, que evita cualquier rama potencial.

Ninguna de las otras soluciones tiene ramas, pero todas se traducen en más instrucciones de CPU que cualquiera de estas, lo que al final del día nos asegura que siempre debemos escribir codigo sencillo y dejar que el compilador lo optimice para nosotros.

  • cmovge es una declaración de rama. Mira el resultado de un condicional anterior y toma una acción en consecuencia. Sucede que es una instrucción condicional bastante buena para esto, pero sigue siendo una rama.

    – Flexografía

    11 de noviembre de 2011 a las 19:07

  • @awoodland: No creo que puedas llamar a eso un rama, el flujo de código no puede ir en dos direcciones. Sí tiene en cuenta el valor anterior para producir uno u otro resultado, pero no puede ser mal predichono tendrá que vaciar la tubería de instrucciones… Probablemente será más lento que otras instrucciones (no se puede reordenar, la ejecución depende de la ejecución anterior, por lo que no se puede paralelizar con él…) pero no ramaa menos que me esté perdiendo algo aquí.

    – David Rodríguez – dribeas

    11 de noviembre de 2011 a las 22:19


  • Su comportamiento depende del registro de condiciones que yo habría dicho que era la definición misma de una rama. Lógicamente, su comportamiento se parece a una rama: los valores en la memoria pueden convertirse en una de dos cosas después de que se haya completado la instrucción. Si eso se puede predecir y, en consecuencia, se puede predecir mal, estoy menos seguro de los diseños de procesadores actuales. No es inconcebible que una predicción de la ruta de “no hacer nada” pueda hacerse de manera errónea y la predicción/predicción errónea no es un requisito previo para que una instrucción sea una rama de todos modos. (Estoy de acuerdo en que responde la pregunta, no es una declaración condicional)

    – Flexografía

    11 de noviembre de 2011 a las 22:30

  • @awoodland: Tengo una comprensión diferente de lo que es un rama es, pero no soy un experto ensamblador. Para mí, es un punto en el código en el que la siguiente instrucción (nota: no el resultado de la instrucción, sino la siguiente instrucción) puede ser una de un conjunto (es decir, un salto condicional), y el problema asociado es que la tubería de instrucción del procesador podría tener que ser zanja en el caso de una predicción errónea. En este caso, ya sea que el valor del registro cambie o no, la siguiente instrucción siempre se conoce, y ya sea que el valor se actualice o no, la canalización de instrucciones se puede utilizar de la mejor manera.

    – David Rodríguez – dribeas

    12 de noviembre de 2011 a las 19:55

avatar de usuario
keith thompson

ACTUALIZAR: Mirando esto 4 años después, veo que falla gravemente si dos o más de los valores resultan ser iguales. reemplazando > por >= cambia el comportamiento, pero no soluciona el problema. Es posible que aún se pueda salvar, por lo que no lo eliminaré todavía, pero no lo use en el código de producción.


Bien, aquí está el mío:

int max3(int a, int b, int c)
{
    return a * (a > b & a > c) +
           b * (b > a & b > c) +
           c * (c > a & c > b);
}

Tenga en cuenta que el uso de & en vez de && evita cualquier código condicional; se basa en el hecho de que > siempre da 0 o 1. (El código generado para a > b podría implicar saltos condicionales, pero no son visibles desde C.)

int fast_int_max(int a, int b)
{
    int select= -(a < b);
    unsigned int b_mask= select, a_mask= ~b_mask;

    return (a&a_mask)|(b&b_mask);
}

int fast_int_max3(int a, int b, int c)
{
    return fast_int_max(a, fast_int_max(b, c));
}

avatar de usuario
gsk

Los operadores con valores booleanos (incluidos <, &&, etc.) generalmente se traducen en operaciones condicionales a nivel de código de máquina, por lo que no cumple con el espíritu del desafío. Aquí hay una solución que cualquier compilador razonable traduciría solo en instrucciones aritméticas sin saltos condicionales (suponiendo que long tenga más bits que int y que long sea 64 bits). La idea es que "m" capture y replique el bit de signo de b - a, de modo que m sea todos los bits 1 (si a > b) o todos los bits cero (si a <= b). Tenga en cuenta que long se usa para evitar el desbordamiento. Si por alguna razón sabe que b - a no se desborda ni se desborda, entonces no es necesario el uso de long.

int max(int a, int b)
{
    long d = (long)b - (long)a;
    int m = (int)(d >> 63);
    return a & m | b & ~m;
}

int max(int a, int b, int c)
{
    long d;
    int m;
    d = (long)b - (long)a;
    m = (int)(d >> 63);
    a = a & m | b & ~m;
    d = (long)c - (long)a;
    m = (int)(d >> 63);
    return a & m | c & ~m;
}

avatar de usuario
Lee Louviere

Sin condicionales. Sólo un yeso a uint. Solución perfecta.

int abs (a) { return (int)((unsigned int)a); }
int max (a, b) { return (a + b + abs(a - b)) / 2; }
int min (a, b) { return (a + b - abs(a - b)) / 2; }


void sort (int & a, int & b, int & c)
{
   int max = max(max(a,b), c);
   int min = min(min(a,b), c);
   int middle = middle = a + b + c - max - min;
   a = max;
   b = middle;
   c = min;
}

  • 1) sort (int & a, int & b, int & c) no es una sintaxis C válida. 2) a-b desbordamientos que conducen a UB en C, para aproximadamente la mitad de todos a,b combinaciones

    – chux – Reincorporar a Monica

    14/09/2015 a las 17:51

  • @chux Desde lo alto de mi cabeza, diría que es solo una cuarta parte de todas las combinaciones. Pasando de 0 (sin desbordamiento posible) a MAX_INT (la mitad de todas las combinaciones causan desbordamiento). El resultado debe estar en el medio. Lo mismo ocurre con 0 a MIN_INT

    –Kami Kaze

    16 de noviembre de 2018 a las 10:40


¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad