Erklären Sie dieses Snippet, das das Maximum von zwei Ganzzahlen findet, ohne if-else oder einen anderen Vergleichsoperator zu verwenden?

Lesezeit: 6 Minuten

Benutzeravatar von SuperMan
Übermensch

Finden Sie das Maximum von zwei Zahlen. Sie sollten if-else oder andere Vergleichsoperatoren nicht verwenden. Ich habe diese Frage im Online-Schwarzen Brett gefunden, also dachte ich, ich sollte in StackOverflow fragen

BEISPIEL Eingabe: 5, 10 Ausgabe: 10

Ich habe diese Lösung gefunden, kann mir jemand helfen, diese Codezeilen zu verstehen

int getMax(int a, int b) {  
    int c = a - b;  
    int k = (c >> 31) & 0x1;  
    int max = a - k * c;  
    return max;  
}

  • Ich würde in Erwägung ziehen, mir das Vorzeichen-Bit-Cheaten anzusehen, da es im Grunde dasselbe ist, wofür der Prozessor arbeitet <.

    – sternenblau

    23. Januar 2011 um 9:08 Uhr

  • Zumindest für C++ ab 5.8.3, Diskussion von E1 >> E2: “Wenn E1 einen vorzeichenbehafteten Typ und einen negativen Wert hat, ist der resultierende Wert implementierungsdefiniert.”, also kann sich “c >> 31” verschieben oder nicht ein Vorzeichenbit vom höchstwertigen zum niederwertigsten Bit….

    – Toni Delroy

    23. Januar 2011 um 16:15 Uhr


  • und es ist nicht abzusehen, dass Bit 31 sowieso das Vorzeichenbit ist.

    – Antti Haapala – Слава Україні

    24. September 2016 um 21:58 Uhr

  • Wie auch immer, diese Frage sollte geschlossen werden, da niemand den Fragetext oder das Tag C liest.

    – Antti Haapala – Слава Україні

    24. September 2016 um 21:59 Uhr

  • Nur weil es sonst niemand bemerkt hat. Dies ist der berühmte Bit-Twiddling-Hack, der gefunden wurde hierin verschleierter Form.

    – kartisch

    17. Juli 2017 um 13:39 Uhr

Benutzeravatar von templatetypedef
Vorlagentypdef

int getMax(int a, int b) {
    int c = a - b;
    int k = (c >> 31) & 0x1;
    int max = a - k * c;
    return max;
}

Lassen Sie uns das sezieren. Diese erste Zeile scheint einfach zu sein – sie speichert die Differenz von a und b. Dieser Wert ist negativ, wenn a < b und ist ansonsten nichtnegativ. Aber hier gibt es tatsächlich einen Fehler – wenn die Differenz der Zahlen a und b so groß ist, dass es nicht in eine ganze Zahl passt, führt dies zu undefiniertem Verhalten – oops! Nehmen wir also an, das passiert hier nicht.

In der nächsten Zeile, die ist

int k = (c >> 31) & 0x1;

Die Idee ist zu überprüfen, ob der Wert von c ist negativ. In praktisch allen modernen Computern werden Zahlen in einem Format namens gespeichert Zweierkomplement wobei das höchste Bit der Zahl 0 ist, wenn die Zahl positiv ist, und 1, wenn die Zahl negativ ist. Außerdem sind die meisten Ganzzahlen 32 Bit. (c >> 31) verschiebt die Zahl um 31 Bit nach unten, wobei das höchste Bit der Zahl an der Stelle für das niedrigste Bit bleibt. Der nächste Schritt, diese Zahl zu nehmen und sie mit 1 UND zu verknüpfen (deren binäre Darstellung überall außer dem letzten Bit 0 ist), löscht alle höheren Bits und gibt Ihnen nur das niedrigste Bit. Da das niedrigste Bit von c >> 31 ist das höchste Bit von cliest dies das höchste Bit von c entweder als 0 oder 1. Da das höchste Bit 1 ist, iff c 1 ist, ist dies eine Möglichkeit zu prüfen, ob c negativ (1) oder positiv (0) ist. Kombiniert man diese Argumentation mit der obigen, k ist 1 wenn a < b und ist sonst 0.

Der letzte Schritt ist, dies zu tun:

int max = a - k * c;

Wenn a < bdann k == 1 und k * c = c = a - bund so

a - k * c = a - (a - b) = a - a + b = b

Welches ist das richtige Maximum, da a < b. Ansonsten, wenn a >= bdann k == 0 und

a - k * c = a - 0 = a

Das ist auch die richtige max.

  • All dies unter der Annahme, dass keine Überläufe auftreten.

    – Peter Taylor

    23. Januar 2011 um 7:48 Uhr

  • @templatetypedef, angenommen a = 0x80000000 (der Mindestwert eines int) und b = 1. Was ist c?

    – Peter Taylor

    23. Januar 2011 um 7:52 Uhr


  • @Peter Taylor- Das ist ein guter Punkt. Beachten Sie, dass ich diese Antwort nicht gefunden habe; Ich habe nur den OP-Code erklärt. 🙂 Aber Sie haben Recht, dass dies kaputt geht, wenn die Zahlen zu weit auseinander liegen.

    – Vorlagentypdef

    23. Januar 2011 um 7:53 Uhr

  • @templatetypedef, ich weiß: Ich war gerade dabei, eine sehr ähnliche Antwort zu schreiben, als Sie Ihre gepostet haben. Ich habe nur darauf hingewiesen, zugunsten von OP.

    – Peter Taylor

    23. Januar 2011 um 7:58 Uhr

  • @Ani, das oberste Bit wird in jede Position verschoben, die es durchläuft. Die Alternative wäre max = a + (c >> 31) * c

    – Peter Taylor

    23. Januar 2011 um 8:00 Uhr

Auf geht’s: (a + b) / 2 + |a - b| / 2

  • Kennen Sie die mathematische Logik dahinter?

    – Senthil Kumaran

    23. Januar 2011 um 7:50 Uhr

  • @mike.did: Kannst du |a – b| machen? ohne Bedingungen?

    – Vorlagentypdef

    23. Januar 2011 um 7:52 Uhr

  • Es ist ziemlich weit hergeholt anzunehmen, dass der absolute Wert ein Operator ist, der für dieses Problem verwendet werden kann. Es ist mathematisch gesehen eine gute Antwort, aber ich bezweifle, dass sie akzeptiert würde.

    – Keith Irwin

    23. Januar 2011 um 7:56 Uhr

  • -1 Falsch bei Ints, zum Beispiel (3 + 2) / 2 + |3 - 2| / 2 = 2 + 0 = 2 != 3.

    – sternenblau

    23. Januar 2011 um 9:06 Uhr

  • @starblue: ((3+2) + |3-2|)/2 = 3 Sieht von hier aus genau richtig aus.

    – Michael Foukarakis

    23. Januar 2011 um 12:16 Uhr

Benutzeravatar von Prasoon Saurav
Prasun Saurav

Verwenden Sie bitweise Hacks

r = x ^ ((x ^ y) & -(x < y)); // max(x, y)

Wenn Sie das wissen INT_MIN <= x - y <= INT_MAX, dann kannst du folgendes verwenden, was schneller geht, weil (x - y) muss nur einmal ausgewertet werden.

r = x - ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1))); // max(x, y)

Quelle : Bit Twiddling Hacks von Sean Eron Anderson

  • Beachten Sie, dass der erste Vorschlag die Beschränkung “kein Vergleichsoperator” durchbricht.

    – Matthias M.

    24. Januar 2011 um 14:26 Uhr

Benutzeravatar von CashCow
Goldesel

(sqrt( a*a + b*b - 2*a*b ) + a + b) / 2

Dies basiert auf der gleichen Technik wie die Lösung von mike.dld, aber es ist hier weniger “offensichtlich”, was ich tue. Eine “abs” -Operation sieht so aus, als würden Sie das Vorzeichen von etwas vergleichen, aber ich nutze hier die Tatsache aus, dass sqrt () Ihnen immer die positive Quadratwurzel zurückgibt, also quadriere ich (ab) und schreibe es vollständig aus dann Quadrat- wieder rooten, a+b addieren und durch 2 dividieren.

Sie werden sehen, dass es immer funktioniert: z. B. das Beispiel des Benutzers von 10 und 5, Sie erhalten sqrt (100 + 25 – 100) = 5, dann addieren Sie 10 und 5 ergibt 20 und dividiert durch 2 ergibt 10.

Wenn wir 9 und 11 als unsere Zahlen verwenden, erhalten wir (sqrt(121 + 81 – 198) + 11 + 9)/2 = (sqrt(4) + 20) / 2 = 22/2 = 11

Benutzeravatar des Anfängers
Anfänger

Die einfachste Antwort ist unten.

#include <math.h>

int Max(int x, int y)
{
    return (float)(x + y) / 2.0 + abs((float)(x - y) / 2);
}

int Min(int x, int y)
{
    return (float)(x + y) / 2.0 - abs((float)(x - y) / 2);
}

Benutzeravatar von Jared Burrows
Jared Burrows

int max(int i, int j) {
    int m = ((i-j) >> 31);
    return (m & j) + ((~m) & i);
}

Diese Lösung vermeidet Multiplikation. m ist entweder 0x00000000 oder 0xffffffff

Verwenden Sie die wechselnde Idee, um das von anderen gepostete Zeichen zu extrahieren. Hier ist ein anderer Weg:

max (a, b) = new[] { a, b } [((a - b) >> 31) & 1]

Dies schiebt die beiden Zahlen in ein Array mit der maximalen Zahl, die durch das Array-Element gegeben ist, dessen Index das Vorzeichenbit der Differenz zwischen den beiden Zahlen ist.

Beachten Sie Folgendes:

  1. Der Unterschied (a - b) kann überlaufen.
  2. Wenn die Nummern unsigned sind und die >> Operator bezieht sich auf a logisch Rechtsverschiebung, die & 1 ist unnötig.

1418630cookie-checkErklären Sie dieses Snippet, das das Maximum von zwei Ganzzahlen findet, ohne if-else oder einen anderen Vergleichsoperator zu verwenden?

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy