Trouver un maximum de trois nombres en C sans utiliser l’instruction conditionnelle et l’opérateur ternaire

Je dois trouver un maximum de trois numéros fournis par l’utilisateur, mais avec certaines ressortingctions. Ce n’est pas autorisé à utiliser n’importe quelle instruction conditionnelle. J’ai essayé d’utiliser l’opérateur ternaire comme ci-dessous.

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

Mais encore une fois, son utilisation est limitée à l’opérateur ternaire. Maintenant, je n’ai aucune idée de comment faire cela?

    Profitant du court-circuit dans les expressions booléennes:

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

    Explication:

    Dans l'opération AND booléenne telle que x && y , y est évalué si et seulement si x est vrai. Si x est faux, alors y n'est pas évalué, car l'expression entière serait fausse, ce qui peut être déduit sans même évaluer y . C'est ce qu'on appelle un court-circuit lorsque la valeur d'une expression booléenne peut être déduite sans évaluer tous les opérandes qu'elle contient.

    Appliquez ce principe au code ci-dessus. Au départ, m est a . Maintenant, si (m < b) est vrai, alors cela signifie que b est supérieur à m (ce qui est en fait a ), de sorte que la seconde sous-expression (m = b) est évaluée et que m est défini sur b . Si toutefois (m < b) est faux, alors la deuxième sous-expression ne sera pas évaluée et m restra a (ce qui est supérieur à b ). De manière similaire, la seconde expression est évaluée (sur la ligne suivante).

    En bref, vous pouvez lire l'expression (m < x) && (m = x) comme suit: mettez m sur x si et seulement si m est inférieur à x c'est-à-dire que (m < x) est vrai. J'espère que cela vous aide à comprendre le code.

    Code de test:

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

    Sortie:

     3 3 3 

    Notez l'implémentation de max donne des avertissements car les expressions évaluées ne sont pas utilisées:

    prog.c: 6: warning: la valeur calculée n'est pas utilisée
    prog.c: 7: attention: la valeur calculée n'est pas utilisée

    Pour éviter ces avertissements (inoffensifs), vous pouvez implémenter max comme:

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

    Le truc, c’est que maintenant nous exprimons les expressions booléennes, ce qui entraîne la suppression des avertissements :

    En supposant que vous avez affaire à des entiers, que diriez-vous:

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

    Juste pour append une autre alternative pour éviter l’exécution conditionnelle (qui n’est pas celle que j’utiliserais, mais qui semblait absente de l’ensemble des solutions):

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

    L'approche utilise (comme la plupart des autres), le fait que le résultat d'une expression booléenne converti en int donne 0 ou 1. La version simplifiée pour deux valeurs serait:

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

    Si l'expression a est correcte, nous retournons b , soigneusement stocké dans le premier index du tableau de recherche. Si l'expression renvoie false, nous renvoyons a élément stocké en tant qu'élément 0 du tableau de recherche. En utilisant ceci comme bloc de construction, vous pouvez dire:

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

    Ce qui peut être transformé sortingvialement en code ci-dessus en évitant le deuxième appel au max interne en utilisant le résultat déjà stocké dans lookup[0] et en insérant l'appel initial dans max(int,int) .


    (Cette partie est juste une autre preuve que vous devez mesurer avant de tirer des conclusions, voir l'édition à la fin)

    En ce qui concerne ce que je voudrais réellement utiliser ... eh bien, probablement celui de @Foo Baa ici modifié pour utiliser une fonction inline plutôt qu'une macro. L'option suivante serait soit celle-ci, soit celle de @MSN ici .

    Le dénominateur commun de ces trois solutions qui ne figurent pas dans la réponse acceptée est qu’elles évitent non seulement la construction syntaxique de if ou l’opérateur ternaire ?: , Mais qu’elles évitent également toute ramification , ce qui peut avoir une incidence sur les performances. Le prédicteur de twig dans la CPU ne peut pas manquer s'il n'y a pas de twig.


    Lorsque vous considérez la performance, mesurez d'abord, puis réfléchissez

    En fait, j'ai implémenté quelques-unes des différentes options pour un maximum de 2 voies et analysé le code généré par le compilateur. Les trois solutions suivantes génèrent le même code d'assemblage:

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

    Ce qui n’est pas surprenant, puisque les trois représentent exactement la même opération. Le bit d’information intéressant est que le code généré ne contient aucune twig. La mise en œuvre est simple avec l’instruction cmovge (test réalisé avec g ++ sur une plate-forme 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 

    L'astuce réside dans l'instruction de déplacement conditionnel, qui évite toute twig potentielle.

    Aucune des autres solutions n’a de twig, mais toutes se traduisent par plus d’instructions cpu que par aucune de celles-ci, ce qui au bout du compte nous assure que nous devrions toujours écrire du code simple et laisser le compilateur l’optimiser pour nous.

    MISE À JOUR: En regardant cela 4 ans plus tard, je constate que cela échoue si deux ou plusieurs valeurs sont égales. Remplacer > par >= modifie le comportement, mais ne résout pas le problème. Il est peut-être encore récupérable, donc je ne vais pas le supprimer pour le moment, mais ne l’utilisez pas dans le code de production.


    Ok, voici le mien:

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

    Notez que l’utilisation de & plutôt que && évite tout code conditionnel; il se base sur le fait que > renvoie toujours 0 ou 1. (Le code généré pour a > b peut impliquer des sauts conditionnels, mais ils ne sont pas visibles depuis 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)); } 

    Les opérateurs de valeur booléens (y compris <, &&, etc.) se traduisent généralement par des opérations conditionnelles au niveau du code machine. Ne remplissez donc pas l'esprit du défi. Voici une solution que tout compilateur raisonnable traduirait uniquement en instructions arithmétiques sans sauts conditionnels (en supposant que long a plus de bits que int et que long a 64 bits). L'idée est que "m" capture et reproduit le bit de signe de b - a, donc m est égal à tous les 1 bits (si a> b) ou à tous les bits zéro (si a <= b). Notez que long est utilisé pour éviter les débordements. Si, pour une raison quelconque, vous savez que b - a ne dépasse pas / ne sous-alimente pas, l'utilisation de long n'est pas nécessaire.

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

    Aucun conditionnel. Seul un casting à uint. Solution parfaite.

     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; } 
     #include "stdafx.h" #include  int main() { int x,y,z; scanf("%d %d %d", &x,&y, &z); int max = ((x+y) + abs(xy)) /2; max = ((max+z) + abs(max-z)) /2; printf("%d ", max); return 0; } 

    Vous pouvez utiliser ce code pour trouver le plus grand des deux:

     max{a,b} = abs(ab)/2 + (a+b)/2 

    puis utilisez-le à nouveau pour trouver le troisième numéro:

     max{a,b,c} = max(a,max(b,c)) 

    Voir que cela fonctionne pour les nombres positifs que vous pouvez changer pour travailler aussi pour les nombres négatifs.

    Aucune instruction conditionnelle , juste des boucles et des assignations. Et complètement différent des réponses des autres 🙂

     while (a > b) { while (a > c) { tmp = a; goto finish; } tmp = c; goto finish; } while (b > c) { tmp = b; goto finish; } tmp = c; finish: max = tmp; 
     int compare(int a,int b, intc) { return (a > b ? (a > c ? a : c) : (b > c ? b : c)) } 

    Essaye ça.

     #include "stdio.h" main() { int a,b,c,rmvivek,arni,csc; printf("enter the three numbers"); scanf("%d%d%d",&a,&b,&c); printf("the biggest value is %d",(a>b&&a>c?a:b>c?b:c)); } 
     max = a > b ? ( a > c ? a : c ) : ( b > c ? b : c ) ;