Trouver le maximum de deux nombres sans l'aide de if-else ou de tout autre opérateur de comparaison

Question

Trouver le maximum de deux nombres. Vous ne devriez pas utiliser des if-else ou de tout autre opérateur de comparaison. J'ai trouvé cette question sur le babillard en ligne, alors j'ai pensé que je devrais demander à StackOverflow

EXEMPLE Entrée: 5, 10 Sortie: 10

J'ai trouvé cette solution, quelqu'un peut-il m'aider à comprendre ces lignes de code

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

Answer 1

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

Nous allons disséquer ce. Cette première ligne est simple: il stocke la différence de a et b. Cette valeur est négative si l' a < b et est non négatif sinon.

Dans la ligne suivante:

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

l'idée est de vérifier si la valeur de c est négatif. Dans pratiquement tous les ordinateurs modernes, les nombres sont stockés dans un format appelé en complément à deux , dans lequel le bit le plus élevé du nombre est 0 si le nombre est positif et 1 si le nombre est négatif. En outre, la plupart des entiers de 32 bits. (c >> 31) décale le numéro 31 bits, laissant le bit le plus élevé du nombre dans le spot pour le bit de poids faible. La prochaine étape de la prise de ce nombre et de la ANDing avec 1 (dont la représentation binaire est 0 partout, sauf le dernier bit) efface tous les bits supérieurs et vous donne juste le bit de poids faible. Depuis le bit de poids faible de c >> 31 est le bit le plus élevé de l' c, ce lit le bit le plus élevé de l' c soit 0 ou 1. Depuis le bit le plus élevé est de 1 iff c est de 1, c'est un moyen de vérifier si c est négatif (1) ou positive (0). La combinaison de ce raisonnement ci-dessus, k est de 1 cas a < b et 0 sinon.

La dernière étape est de faire ceci:

int max = a - k * c;

Si a < b, alors k == 1 et k * c = c = a - b, et ainsi de

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

Qui est le bon max, depuis a < b. Si, au contraire, a >= b, alors k == 0 et

a - k * c = a - 0 = a

Ce qui est également le bon max.

Answer 2

Nous y voilà: (a + b) / 2 + |a - b| / 2

Answer 3

Utiliser des hacks and au niveau du bit

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

Si vous savez qu' INT_MIN <= x - y <= INT_MAX, , alors vous pouvez utiliser la commande suivante, qui est plus rapide, car (x - y) ne doit être évaluée une fois.

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

Source : Bit se Tourner les Hacks par Sean Eron Anderson

Answer 4

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

Ceci est basé sur la même technique que mikedld la solution ci-dessus, mais il est moins "évident" voici ce que je fais. "Abs" opération dirait que vous êtes en comparant le signe de quelque chose, mais je suis ici en tirant parti du fait que sqrt() retournera toujours vous la racine carrée positive donc, je suis en quadrature (a-b) écrire, en plein carré-l'enracinement de nouveau, en ajoutant un+b et en divisant par 2.

Vous verrez qu'il fonctionne toujours: par exemple, l'utilisateur exemple de 10 et 5 vous obtenez sqrt(100 + 25 - 100) = 5 puis ajouter 10 et 5 vous donne 20 et diviser par 2 vous donne 10.

Si nous utilisons les 9 et 11 que notre nombre, nous aurions (sqrt(121 + 81 - 198) + 11 + 9)/2 = (sqrt(4) + 20) / 2 = 22/2 = 11

Answer 5

La réponse la plus simple est ci-dessous.

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