Finden Sie das Maximum von zwei Zahlen. Sie sollten if-else oder einen anderen Vergleichsoperator nicht verwenden. Ich habe diese Frage im Online-Bulletin Board gefunden, daher dachte ich, ich sollte sie in StackOverflow stellen
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;
}
<
.Antworten:
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 analysieren. Diese erste Zeile scheint unkompliziert zu sein - sie speichert den Unterschied von
a
undb
. Dieser Wert ist negativa < b
und ansonsten nicht negativ . Es gibt tatsächlich einen Fehler hier - wenn die Differenz der Zahlena
undb
so groß ist , dass es nicht in eine ganze Zahl passt, dies zu undefinierten Verhalten führen - oops! Nehmen wir also an, dass dies hier nicht der Fall ist.In der nächsten Zeile ist das
int k = (c >> 31) & 0x1;
Die Idee ist zu überprüfen, ob der Wert von
c
negativ ist. In praktisch allen modernen Computern werden Zahlen in einem Format gespeichert, das als Zweierkomplement bezeichnet wird, wobei das höchste Bit der Zahl 0 ist, wenn die Zahl positiv ist, und 1, wenn die Zahl negativ ist. Darüber hinaus sind die meisten Ints 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 verbleibt. Der nächste Schritt, diese Zahl zu nehmen und 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 vonc >> 31
das höchste Bit von istc
, liest dies das höchste Bitc
entweder als 0 oder 1. Da das höchste Bit 1c
ist, wennf 1 ist, ist dies eine Möglichkeit zu prüfen, obc
ist negativ (1) oder positiv (0). Die Kombination dieser Argumentation mit der obigenk
ist 1, wenna < b
und andernfalls 0.Der letzte Schritt ist dies:
int max = a - k * c;
Wenn
a < b
, dannk == 1
undk * c = c = a - b
und soWelches ist das richtige Maximum, da
a < b
. Ansonsten wenna >= b
, dannk == 0
unda - k * c = a - 0 = a
Welches ist auch die richtige max.
quelle
max = a + (c >> 31) * c
Auf geht's:
(a + b) / 2 + |a - b| / 2
quelle
(3 + 2) / 2 + |3 - 2| / 2 = 2 + 0 = 2 != 3
.Verwenden Sie bitweise Hacks
r = x ^ ((x ^ y) & -(x < y)); // max(x, y)
Wenn Sie das wissen,
INT_MIN <= x - y <= INT_MAX,
können Sie Folgendes verwenden, was schneller ist, da es(x - y)
nur einmal ausgewertet werden muss.r = x - ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1))); // max(x, y)
Quelle: Bit Twiddling Hacks von Sean Eron Anderson
quelle
(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) vollständig und dann quadriert. Rooting erneut, Hinzufügen von a + b und Teilen durch 2.
Sie werden sehen, dass es immer funktioniert: Wenn Sie beispielsweise im Beispiel des Benutzers 10 und 5 sqrt (100 + 25 - 100) = 5 erhalten, addieren Sie 10 und 5 ergibt 20 und dividieren 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
quelle
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); }
quelle
int max(int i, int j) { int m = ((i-j) >> 31); return (m & j) + ((~m) & i); }
Diese Lösung vermeidet die Multiplikation. m ist entweder 0x00000000 oder 0xffffffff
quelle
Verwenden Sie die Verschiebungsidee, um das von anderen gepostete Zeichen zu extrahieren.
max (a, b) = new[] { a, b } [((a - b) >> 31) & 1]
Dadurch werden die beiden Zahlen in ein Array mit der maximalen Anzahl verschoben, die vom Array-Element angegeben wird, dessen Index das Vorzeichenbit der Differenz zwischen den beiden Zahlen ist.
Beachten Sie Folgendes:
(a - b
kann überlaufen.>>
Operator auf eine logische Rechtsverschiebung verweist ,& 1
ist dies nicht erforderlich.quelle
Hier ist, wie ich denke, ich würde den Job machen. Es ist nicht so lesbar, wie Sie vielleicht möchten, aber wenn Sie mit "Wie mache ich X ohne die offensichtliche Art, X zu machen, beginnen, müssen Sie das irgendwie erwarten. Theoretisch gibt dies auch eine gewisse Portabilität auf, aber Sie". Ich muss ein ziemlich ungewöhnliches System finden, um ein Problem zu erkennen.
#define BITS (CHAR_BIT * sizeof(int) - 1) int findmax(int a, int b) { int rets[] = {a, b}; return rets[unsigned(a-b)>>BITS]; }
Dies hat einige Vorteile gegenüber dem in der Frage gezeigten. Zunächst wird die korrekte Größe der Verschiebung berechnet, anstatt für 32-Bit-Ints fest codiert zu sein. Zweitens können wir bei den meisten Compilern erwarten, dass die gesamte Multiplikation zur Kompilierungszeit erfolgt. Zur Laufzeit bleibt also nur eine triviale Bitmanipulation (Subtrahieren und Verschieben), gefolgt von Laden und Zurückgeben. Kurz gesagt, dies ist mit ziemlicher Sicherheit ziemlich schnell, selbst auf dem kleinsten Mikrocontroller, auf dem die ursprünglich verwendete Multiplikation zur Laufzeit durchgeführt werden musste. Während es auf einem Desktop-Computer wahrscheinlich ziemlich schnell ist, ist es oft ziemlich schnell etwas langsamer auf einem kleinen Mikrocontroller.
quelle
Folgendes tun diese Zeilen:
c ist ab. wenn c negativ ist, ist a <b.
k ist das 32. Bit von c, das das Vorzeichenbit von c ist (unter der Annahme von 32-Bit-Ganzzahlen. Wenn dies auf einer Plattform mit 64-Bit-Ganzzahlen erfolgt, funktioniert dieser Code nicht). Es wird 31 Bits nach rechts verschoben, um die 31 Bits ganz rechts zu entfernen, wobei das Vorzeichenbit ganz rechts verbleibt, und dann mit 1 kombiniert, um alle Bits links zu entfernen (die mit 1s gefüllt werden, wenn c negativ ist). Also ist k 1, wenn c negativ ist, und 0, wenn c positiv ist.
Dann ist max = a - k * c. Wenn c 0 ist, bedeutet dies a> = b, also ist max a - 0 * c = a. Wenn c 1 ist, bedeutet dies, dass a <b und dann a - 1 * c = a - (a - b) = a - a + b = b.
Insgesamt wird nur das Vorzeichenbit des Unterschieds verwendet, um zu vermeiden, dass Operationen größer oder kleiner als verwendet werden. Es ist ehrlich gesagt ein wenig albern zu sagen, dass dieser Code keinen Vergleich verwendet. c ist das Ergebnis des Vergleichs von a und b. Der Code verwendet einfach keinen Vergleichsoperator. Ähnliches können Sie in vielen Assemblycodes tun, indem Sie einfach die Zahlen subtrahieren und dann basierend auf den im Statusregister festgelegten Werten springen.
Ich sollte auch hinzufügen, dass alle diese Lösungen davon ausgehen, dass die beiden Zahlen ganze Zahlen sind. Wenn es sich um Floats, Doubles oder etwas Komplizierteres handelt (BigInts, Rational Numbers usw.), müssen Sie wirklich einen Vergleichsoperator verwenden. Bit-Tricks reichen für diese im Allgemeinen nicht aus.
quelle
getMax () Funktion ohne logische Operation-
int getMax(int a, int b){ return (a+b+((a-b)>>sizeof(int)*8-1|1)*(a-b))/2; }
Erläuterung:
Lasst uns das 'Maximum' in Stücke zerschlagen,
max = ( max + max ) / 2 = ( max + (min+differenceOfMaxMin) ) / 2 = ( max + min + differenceOfMaxMin ) / 2 = ( max + min + | max - min | ) ) / 2
Die Funktion sollte also so aussehen:
getMax(a, b) = ( a + b + absolute(a - b) ) / 2
Jetzt,
absolute(x) = x [if 'x' is positive] or -x [if 'x' is negative] = x * ( 1 [if 'x' is positive] or -1 [if 'x' is negative] )
Damit,
absolute(x) = x * ( 1 [if 'x' is positive] or -1 [if 'x' is negative] ) = x * ( ( x >> (numberOfBitsInInteger-1) ) | 1 ) = x * ( ( x >> ((numberOfBytesInInteger*bitsInOneByte) - 1) ) | 1 ) = x * ( ( x >> ((sizeOf(int)*8) - 1) ) | 1 )
Schließlich,
getMax(a, b) = ( a + b + absolute(a - b) ) / 2 = ( a + b + ((a-b) * ( ( (a-b) >> ((sizeOf(int)*8) - 1) ) | 1 )) ) / 2
Ein anderer Weg -
int getMax(int a, int b){ int i[] = {a, b}; return i[( (i[0]-i[1]) >> (sizeof(int)*8 - 1) ) & 1 ]; }
quelle
statisch int mymax (int a, int b)
{ int[] arr; arr = new int[3]; arr[0] = b; arr[1] = a; arr[2] = a; return arr[Math.Sign(a - b) + 1]; }
Wenn b> a dann (ab) negativ ist, gibt das Vorzeichen -1 zurück. Durch Addition von 1 erhalten wir den Index 0, der b ist. Wenn b = a, dann ist ab 0, +1 ergibt 1 Index, so dass es keine Rolle spielt Wenn wir a oder b zurückgeben, wenn a> b, dann ist ab positiv und das Vorzeichen gibt 1 zurück. Wenn wir 1 hinzufügen, erhalten wir den Index 2, in dem a gespeichert ist.
quelle
#include<stdio.h> main() { int num1,num2,diff; printf("Enter number 1 : "); scanf("%d",&num1); printf("Enter number 2 : "); scanf("%d",&num2); diff=num1-num2; num1=abs(diff); num2=num1+diff; if(num1==num2) printf("Both number are equal\n"); else if(num2==0) printf("Num2 > Num1\n"); else printf("Num1 > Num2\n"); }
quelle
Der Code, den ich bereitstelle, dient zum Finden des Maximums zwischen zwei Zahlen. Die Zahlen können von einem beliebigen Datentyp sein (Ganzzahl, Gleitkomma). Wenn die eingegebenen Nummern gleich sind, gibt die Funktion die Nummer zurück.
double findmax(double a, double b) { //find the difference of the two numbers double diff=a-b; double temp_diff=diff; int int_diff=temp_diff; /* For the floating point numbers the difference contains decimal values (for example 0.0009, 2.63 etc.) if the left side of '.' contains 0 then we need to get a non-zero number on the left side of '.' */ while ( (!(int_diff|0)) && ((temp_diff-int_diff)||(0.0)) ) { temp_diff = temp_diff * 10; int_diff = temp_diff; } /* shift the sign bit of variable 'int_diff' to the LSB position and find if it is 1(difference is -ve) or 0(difference is +ve) , then multiply it with the difference of the two numbers (variable 'diff') then subtract it with the variable a. */ return a- (diff * ( int_diff >> (sizeof(int) * 8 - 1 ) & 1 )); }
Beschreibung
Das Vorzeichenbit wird als das höchstwertige Bit (MSB) im Speicher gespeichert. Wenn MSB 1 ist und umgekehrt. Um zu überprüfen, ob MSB 1 oder 0 ist, verschieben wir das MSB in die LSB-Position und Bitwise & mit 1, wenn das Ergebnis 1 ist, ist die Zahl -ve sonst nein. ist + ve. Dieses Ergebnis ergibt sich aus der Aussage:
int_diff >> (sizeof (int) * 8 - 1) & 1
Um das Vorzeichenbit vom MSB zum LSB zu erhalten, verschieben wir es nach rechts auf k-1 Bits (wobei k die Anzahl der Bits ist, die zum Speichern einer Ganzzahl im Speicher benötigt werden, die vom Systemtyp abhängt). Hier gibt k = sizeof (int) * 8 als sizeof () die Anzahl der Bytes an, die zum Speichern einer Ganzzahl erforderlich sind, um no zu erhalten. von Bits multiplizieren wir es mit 8. Nach der rechten Verschiebung wenden wir das bitweise & mit 1 an, um das Ergebnis zu erhalten.
Nachdem wir nun das Ergebnis (nehmen wir es als r an) als 1 (für -ve diff) und 0 (für + ve diff) erhalten haben, multiplizieren wir das Ergebnis mit der Differenz der beiden Zahlen. Die Logik lautet wie folgt:
Jetzt gibt es zwei verbleibende Punkte: 1. die Verwendung der while-Schleife und 2. warum ich die Variable 'int_diff' als Ganzzahl verwendet habe. Um diese richtig zu beantworten, müssen wir einige Punkte verstehen:
quelle
Hier sind einige Bit-Twiddling- Methoden, um das Maximum von zwei Integralwerten zu erhalten:
Methode 1
int max1(int a, int b) { static const size_t SIGN_BIT_SHIFT = sizeof(a) * 8 - 1; int mask = (a - b) >> SIGN_BIT_SHIFT; return (a & ~mask) | (b & mask); }
Erläuterung:
a > b
danna - b
positiv ist, ist das Vorzeichenbit0
und die Maske0x00.00
. Andernfallsa < b
soa - b
negativ ist, ist das Vorzeichenbit1
und nach dem Verschieben, erhalten wir eine Maske0xFF..FF
0xFF..FF
, dann~mask
ist0x00..00
und dann ist dieser Wert0
. Ansonsten~mask
ist0xFF..FF
und der Wert ista
0xFF..FF
, dann ist dieser Wertb
. Ansonstenmask
ist0x00..00
und der Wert ist0
.Schließlich:
a >= b
danna - b
positiv ist, bekommen wirmax = a | 0 = a
a < b
danna - b
negativ ist, bekommen wirmax = 0 | b = b
Methode 2
int max2(int a, int b) { static const size_t SIGN_BIT_SHIFT = sizeof(a) * 8 - 1; int mask = (a - b) >> SIGN_BIT_SHIFT; return a ^ ((a ^ b) & mask); }
Erläuterung:
a > b
die Maske ist0x00..00
, ist die Maske sonst0xFF..FF
0x00..00
, dann(a ^ b) & mask
ist0x00..00
0xFF..FF
, dann(a ^ b) & mask
ista ^ b
Schließlich:
a >= b
ja, bekommen wira ^ 0x00..00 = a
a < b
ja, bekommen wira ^ a ^ b = b
quelle
// In C # können Sie die Mathematikbibliothek verwenden, um die Min- oder Max-Funktion auszuführen
using System;
Klasse NumberComparator {
static void Main() { Console.Write(" write the first number to compare: "); double first_Number = double.Parse(Console.ReadLine()); Console.Write(" write the second number to compare: "); double second_Number = double.Parse(Console.ReadLine()); double compare_Numbers = Math.Max(first_Number, second_Number); Console.Write("{0} is greater",compare_Numbers); }
}}
quelle
Keine logischen Operatoren, keine Bibliotheken (JS)
function (x, y) { let z = (x - y) ** 2; z = z ** .5; return (x + y + z) / 2 }
quelle
Die in einem Problem beschriebene Logik kann so erklärt werden, dass wenn die 1. Zahl kleiner als 0 ist, subtrahiert wird, andernfalls wird die Differenz von der 1. Zahl subtrahiert, um die 2. Zahl zu erhalten. Ich habe eine weitere mathematische Lösung gefunden, die meines Erachtens etwas einfacher zu verstehen ist.
Betrachtet man a und b als gegebene Zahlen
c=|a/b|+1; d=(c-1)/b; smallest number= a - d*(a-b);
Wiederum besteht die Idee darin, k zu finden, das 0 oder 1 verdorrt, und es mit der Differenz zweier Zahlen zu multiplizieren. Und schließlich sollte diese Zahl von der ersten Zahl subtrahiert werden, um die kleinere der beiden Zahlen zu erhalten. PS: Diese Lösung schlägt fehl, wenn die zweite Zahl Null ist
quelle
Es gibt einen Weg
public static int Min(int a, int b) { int dif = (int)(((uint)(a - b)) >> 31); return a * dif + b * (1 - dif); }
und ein
return (a>=b)?b:a;
quelle
int a=151; int b=121; int k=Math.abs(a-b); int j= a+b; double k1=(double)(k); double j1= (double) (j); double c=Math.ceil(k1/2) + Math.floor(j1/2); int c1= (int) (c); System.out.println(" Max value = " + c1);
quelle
Vermutlich können wir die Zahlen einfach mit ihren bitweisen Vergleichen multiplizieren, z.
int max=(a>b)*a+(a<=b)*b;
quelle