Wie gebe ich programmgesteuert das Maximum von zwei Ganzzahlen zurück, ohne Vergleichsoperatoren zu verwenden und ohne zu verwenden if, elseetc?
Wie gebe ich programmgesteuert das Maximum von zwei Ganzzahlen zurück, ohne Vergleichsoperatoren zu verwenden und ohne if, else usw. zu verwenden?
Lesezeit: 3 Minuten
11436300cookie-checkWie gebe ich programmgesteuert das Maximum von zwei Ganzzahlen zurück, ohne Vergleichsoperatoren zu verwenden und ohne if, else usw. zu verwenden?
HerrDatenbank
Sockel
max: // Setzt MAX(a,b) in a
a -= b;
a &= (~a) >> 31;
a += b;
Und:
int a, b;
min: // Setzt MIN(a,b) in a
a -= b;
a &= a >> 31;
a += b;
aus hier.
-
Was ist mit 64-Bit-Ints oder Ints beliebiger Größe? 🙂
– ADept
22. Oktober 2008 um 20:51 Uhr
-
Dafür abstimmen? Betten Sie es in eine vorlagenbasierte oder polymorphe Inline-Funktion ein – die Übung bleibt dem aufmerksamen Leser überlassen.
– Sockel
22. Oktober 2008 um 20:54 Uhr
-
Per Definition können polymorphe Funktionen nicht inline sein. Sie müssen den Funktionsaufruf von vtable zur Laufzeit auswerten. Aber nette Lösung, funktioniert aber nicht für unsigned ints …
– Greg Rogers
22. Oktober 2008 um 21:27 Uhr
-
Sie sollten erwähnen, dass dies von vorzeichenbehafteten Rechtsverschiebungen abhängt, bei denen das Vorzeichen erhalten bleibt. Dies wird durch den C-Standard afaik nicht gewährleistet. Allerdings funktioniert es unter gcc für mich.
– Freiraum
23. Oktober 2008 um 2:22 Uhr
-
@VinayakGarg – wenn a == b, dann ist der Wert von a bis zum letzten Schritt Null, an diesem Punkt wird er zu b hinzugefügt. Es klappt.
– Hoodaticus
15. Dezember 2016 um 19:49 Uhr
MSN
http://www.graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax
r = x - ((x - y) & -(x < y)); // max(x, y)
Beim rechnerischen Verschieben kann man Spaß haben (x - y) um das Vorzeichenbit zu sättigen, aber das ist normalerweise genug. Oder Sie können das hohe Bit testen, macht immer Spaß.
-
Nun, um ganz pedantisch zu sein, Sie sollten über Verzweigungen sprechen, nicht über Vergleichsoperatoren, da Verzweigungen mit weitaus größerer Wahrscheinlichkeit Leistungsprobleme verursachen. Aber wie auch immer, deshalb habe ich den zusätzlichen Kommentar unten hinzugefügt, da x < y gleichbedeutend ist mit dem Erhalten des hohen Bits von x - y.
– MSN
22. Oktober 2008 um 20:54 Uhr
Dimitris
In der Welt der Mathematik:
max(a+b) = ( (a+b) + |(a-b)| ) / 2
min(a-b) = ( (a+b) - |(a-b)| ) / 2
Abgesehen davon, dass es mathematisch korrekt ist, werden keine Annahmen über die Bitgröße getroffen, wie dies bei Verschiebungsoperationen der Fall sein muss.
|x| steht für den absoluten Wert von x.
Kommentar:
Sie haben Recht, der absolute Wert wurde vergessen. Dies sollte für alle a, b positiv oder negativ gelten
-
Dies scheint nicht richtig zu sein. Beispiel: min(-500, 0)=((-500+0)-(-500-0))/2=(-500+500)/2=0
– Sander
15. Mai 2009 um 8:54 Uhr
-
Versteckst du hier nicht einfach den Vergleich? Seit
abs(x) := x >= 0 ? x : -x. Sie benötigen also trotzdem einen Verzweigungsoperator. Natürlich kann man die Verzweigung mit einer &-Maske verhindern, aber dann müsste man Annahmen über die Bitanzahl der Operanden treffen.– Markusklaas
12. Dezember 2014 um 1:02 Uhr
-
“sollte für alle a,b positiv oder negativ gelten” gilt nicht für
intwiea+bkann leicht überlaufen.– chux – Wiedereinsetzung von Monica
30. August 2015 um 20:18 Uhr
Leer
Ich glaube, ich habe es.
int data[2] = {a,b};
int c = a - b;
return data[(int)((c & 0x80000000) >> 31)];
Würde das nicht funktionieren? Grundsätzlich nehmen Sie die Differenz der beiden und geben dann das eine oder andere basierend auf dem Vorzeichenbit zurück. (Auf diese Weise macht der Prozessor ohnehin größer oder kleiner als.) Wenn also das Vorzeichenbit 0 ist, gib a zurück, da a größer oder gleich b ist. Wenn das Vorzeichenbit 1 ist, gib b zurück, da das Subtrahieren von b von a dazu führte, dass das Ergebnis negativ wurde, was darauf hinweist, dass b größer als a war. Stellen Sie einfach sicher, dass Ihre Ints 32-Bit-signiert sind.
Bobwienholt
return (a > b ? a : b);
oder
int max(int a, int b)
{
int x = (a - b) >> 31;
int y = ~x;
return (y & a) | (x & b);
}
-
Ich denke > ist nicht erlaubt. Auch ?: ist zu sehr wie if-else.
– MrDatabase
22. Oktober 2008 um 20:22 Uhr
-
Bobs Antwort ist eine vernünftige praktische Lösung für die Frage ohne if/else.
– EvilTeach
22. Oktober 2008 um 20:28 Uhr
-
@EvilTeach: Das ?: op impliziert beim Kompilieren einen Vergleich, was das OP nicht wollte.
– Calyth
12. Januar 2009 um 21:48 Uhr
Bartosz Wojcik
Aus dem Artikel “Polymorphic Games” von z0mbie (berühmter Virii-Autor) finden Sie ihn vielleicht nützlich:
#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))
Prost
-
Ich denke > ist nicht erlaubt. Auch ?: ist zu sehr wie if-else.
– MrDatabase
22. Oktober 2008 um 20:22 Uhr
-
Bobs Antwort ist eine vernünftige praktische Lösung für die Frage ohne if/else.
– EvilTeach
22. Oktober 2008 um 20:28 Uhr
-
@EvilTeach: Das ?: op impliziert beim Kompilieren einen Vergleich, was das OP nicht wollte.
– Calyth
12. Januar 2009 um 21:48 Uhr
mspmsp
nicht so schick wie oben… aber…
int getMax(int a, int b)
{
for(int i=0; (i<a) || (i<b); i++) { }
return i;
}
-
Ups, kein Vergleich! doh! 🙂
– mspmsp
22. Oktober 2008 um 20:35 Uhr
-
Ich frage mich auch, ob das „für“ als „wenn, sonst usw.“ ausgelegt werden könnte.
– Christoph Johnson
22. Oktober 2008 um 20:37 Uhr
-1: Warum keine Vergleiche? Scheint mir eine künstliche Frage zu sein.
– Alex Lymann
22. Oktober 2008 um 20:28 Uhr
Warum tauchen diese bizarren Rätsel als Interviewfragen auf? Werden Mechaniker zum Beispiel gefragt, wie sie einen Benzinmotor ohne Zündkerzen zum Laufen bringen würden?
– Michael Burr
22. Oktober 2008 um 20:41 Uhr
Vielleicht ist die Idee, dass der Kandidat die maximale Punktzahl erzielt, indem er fragt, warum in aller Welt irgendjemand daran interessiert wäre, die Antwort zu wissen Compiler Writer hat (a
– Steve Jessop
22. Oktober 2008 um 21:04 Uhr
@Mark: Der Grund, warum ich sage, dass es für Assembler-Programmierer angemessen ist, ist nur, dass Tricks zur Vermeidung von Sprüngen ziemlich üblich sind (es sei denn, Ihre CPU optimiert den Mikrocode wirklich gut). Auf ARM würden Sie zum Beispiel eindeutig Bedingungen verwenden, also wäre die Frage “wie das ohne Verzweigung geht”. Vielleicht.
– Steve Jessop
23. Oktober 2008 um 3:31 Uhr
@Michael Burr: Mindestens ein Mechaniker wurde gefragt, wie man einen Benzinmotor dazu bringt, ohne Zündkerzen zu laufen. Sein Name war „Diesel“.
– MusiGenesis
29. März 2010 um 12:01 Uhr