Finden Sie maximal drei Zahlen in C, ohne die bedingte Anweisung und den ternären Operator zu verwenden

Ich muss maximal drei vom Benutzer bereitgestellte Nummern finden, jedoch mit einigen Einschränkungen. Es ist nicht erlaubt, eine bedingte Anweisung zu verwenden. Ich habe versucht, einen ternären Operator wie unten zu verwenden.

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

Aber auch hier ist es auf die Verwendung des ternären Operators beschränkt. Jetzt bekomme ich keine Ahnung, wie ich das machen soll?

Kurzschließen in booleschen Ausdrücken ausnutzen:

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

Erläuterung:

In Boolesch AND Betrieb wie z x && yy wird ausgewertet dann und nur dann, wenn x ist wahr. Wenn x ist dann falsch y wird nicht ausgewertet, da der gesamte Ausdruck falsch wäre, was auch ohne Auswertung abgeleitet werden kann y. Dies wird als Kurzschließen bezeichnet, wenn der Wert eines booleschen Ausdrucks abgeleitet werden kann, ohne alle darin enthaltenen Operanden auszuwerten.

Wenden Sie dieses Prinzip auf den obigen Code an. Anfänglich m ist a. Wenn jetzt (m < b) stimmt, dann heißt das, b ist größer als m (was eigentlich ist a), also der zweite Unterausdruck (m = b) wird ausgewertet u m ist eingestellt auf b. Wenn doch (m < b) falsch ist, wird der zweite Unterausdruck nicht ausgewertet und m wird bleiben a (was größer ist als b). Auf ähnliche Weise wird der zweite Ausdruck ausgewertet (in der nächsten Zeile).

Kurz gesagt, Sie können den Ausdruck lesen (m < x) && (m = x) wie folgt: einstellen m zu x dann und nur dann, wenn m ist weniger als x dh (m < x) ist wahr. Ich hoffe, das hilft Ihnen, den Code zu verstehen.

Testcode:

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

Ausgabe:

3
3
3

Beachten Sie die Implementierung von max gibt Warnungen aus, weil ausgewertete Ausdrücke nicht verwendet werden:

prog.c:6: Warnung: Berechneter Wert wird nicht verwendet
prog.c:7: Warnung: Berechneter Wert wird nicht verwendet

Um diese (harmlosen) Warnungen zu vermeiden, können Sie implementieren max wie:

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

Der Trick besteht darin, dass wir jetzt die booleschen Ausdrücke in umwandeln voidwodurch die Warnungen unterdrückt werden:

Angenommen, Sie haben es mit ganzen Zahlen zu tun, wie wäre es mit:

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

Nur um eine weitere Alternative hinzuzufügen, um die bedingte Ausführung zu vermeiden (die ich nicht verwenden würde, aber in den Lösungen zu fehlen schien):

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

Der Ansatz nutzt (wie die meisten anderen) die Tatsache, dass das Ergebnis eines booleschen Ausdrucks bei der Konvertierung in int entweder 0 oder 1 ergibt. Die vereinfachte Version für zwei Werte wäre:

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

Wenn der Ausdruck a<b ist richtig, wir kehren zurück b, sorgfältig im ersten Index des Lookup-Arrays gespeichert. Wenn der Ausdruck falsch ergibt, kehren wir zurück a das als Element gespeichert wird 0 des Lookup-Arrays. Wenn Sie dies als Baustein verwenden, können Sie sagen:

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

Was trivial in den obigen Code umgewandelt werden kann, indem der zweite Aufruf des Inneren vermieden wird max unter Verwendung des bereits gespeicherten Ergebnisses in lookup[0] und Einfügen des ursprünglichen Aufrufs an max(int,int).

(Dieser Teil ist nur ein weiterer Beweis, den Sie messen müssen, bevor Sie zu Schlussfolgerungen kommen, siehe die Bearbeitung am Ende.)

Welche würde ich eigentlich verwenden … nun, wahrscheinlich die von @Foo Baa hier, die so modifiziert wurde, dass sie eine Inline-Funktion anstelle eines Makros verwendet. Die nächste Option wäre entweder diese oder die von @MSN hier.

Der gemeinsame Nenner dieser drei Lösungen, die in der akzeptierten Antwort nicht enthalten sind, besteht darin, dass sie nicht nur das syntaktische Konstrukt von vermeiden if oder der ternäre Operator ?:aber das vermeiden sie Verzweigung insgesamt, und das kann sich auf die Leistung auswirken. Das Zweig-Prädiktor in der CPU kann unmöglich fehlen, wenn es keine Verzweigungen gibt.

Wenn Sie Leistung in Betracht ziehen, messen Sie zuerst und denken Sie dann nach

Ich habe tatsächlich einige der verschiedenen Optionen für ein 2-Wege-Max implementiert und den vom Compiler generierten Code analysiert. Die folgenden drei Lösungen generieren denselben Assemblercode:

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

Was nicht verwunderlich ist, da alle drei genau die gleiche Operation darstellen. Die interessante Information ist, dass der generierte Code keine Verzweigung enthält. Die Implementierung ist einfach mit der cmovge anleitung (test durchgeführt mit g++ auf einer intel x64 plattform):

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

Der Trick liegt in der bedingten Bewegungsanweisung, die jede mögliche Verzweigung vermeidet.

Keine der anderen Lösungen hat Verzweigungen, aber alle übersetzen in mehr CPU-Anweisungen als jede dieser Lösungen, was uns am Ende des Tages versichert, dass wir es immer tun sollten einfachen Code schreiben und lassen Sie den Compiler es für uns optimieren.

AKTUALISIEREN: Wenn ich mir das 4 Jahre später anschaue, sehe ich, dass es schlecht versagt, wenn zwei oder mehr der Werte zufällig gleich sind. Ersetzen > durch >= ändert das Verhalten, behebt aber nicht das Problem. Es ist möglicherweise noch zu retten, daher werde ich es noch nicht löschen, aber verwenden Sie es nicht im Produktionscode.

Okay, hier ist meins:

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

Beachten Sie, dass die Verwendung von & statt && vermeidet jeden bedingten Code; es beruht darauf, dass > ergibt immer 0 oder 1. (Der generierte Code für a > b kann bedingte Sprünge beinhalten, aber sie sind von C aus nicht sichtbar.)

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

Boolesche Operatoren (einschließlich <, && usw.) werden normalerweise in bedingte Operationen auf Maschinencodeebene übersetzt, erfüllen Sie also nicht den Geist der Herausforderung. Hier ist eine Lösung, die jeder vernünftige Compiler nur in arithmetische Anweisungen ohne bedingte Sprünge übersetzen würde (vorausgesetzt, long hat mehr Bits als int und long ist 64 Bits). Die Idee ist, dass "m" das Vorzeichenbit von b - a erfasst und repliziert, sodass m entweder alle 1-Bits (wenn a > b) oder alle Null-Bits (wenn a <= b) ist. Beachten Sie, dass long verwendet wird, um einen Überlauf zu vermeiden. Wenn Sie aus irgendeinem Grund wissen, dass b - a nicht über-/unterläuft, dann ist die Verwendung von long nicht erforderlich.

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

Keine Bedingungen. Nur eine Besetzung zu uint. Perfekte Lösung.

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