Maximum de trois entiers utilisant des opérations au niveau des bits?

Comment renvoyer le maximum de trois entiers non signés en n’utilisant que des opérations binarys, comme!, ~, |, &, ^, +, >>, <<. Je ne sais pas où commencer. Toute aide serait appréciée.

modifier:

Je suis seulement autorisé à utiliser les opérations légales données, c’est tout.

/** maxOfThree - Returns the maximum of three integers. * NOTE: x, y, z are all in the range [0, TMax]. * Examples: maxOfThree(1, 2, 3) = 3 * Legal Ops: ! ~ & ^ | + <> * Max Ops: 25 int maxOfThree(int x, int y, int z) { } 

Jetez un coup d’œil à la page ” bidouillages ” et étudiez comment le maximum / le minimum sont appliqués.

Si vous pouvez comprendre comment fonctionne le maximum pour deux nombres, vous pouvez généraliser la casse pour trois nombres.

Permettez-moi de vous expliquer le cas de deux nombres pour obtenir la valeur maximale:


-(a peut renvoyer -1 ou 0, vous pouvez alors avoir 11111111 11111111 11111111 11111111 (-1 dans le complément à deux pour un int) ou 00000000 00000000 00000000 00000000 (-0 == 0 pour un int).

En vous rappelant que a^b^b = a et que a^b^a = b (peu importe l'ordre, c'est l'opération xor ), vous avez cela dans le premier cas:

  • Si a < b vous devez retourner b comme résultat, alors

a ^ ((a ^ b) & -(a < b)) doit être égal à a ^ a ^ b .. et en fait c'est depuis -(a renvoie 11111111 11111111 11111111 11111111 et an-bitwise & exploité sur 11111111 11111111 11111111 11111111 pour un entier non signé laisse le nombre inchangé ... donc a ^ a ^ b = b . C'est le maximum.

  • Si a > b alors a < b est faux, donc (anything & 00000000 00000000 00000000 00000000) ce que vous souhaitez (anything & 00000000 00000000 00000000 00000000) vaut 0. Vous avez donc a ^ 0 , qui est a. Le maximum.

Et enfin nous avons la solution généralisée pour trois nombres:

 #include  int getMax(unsigned int a, unsigned int b, unsigned int c) { int temp = a ^ ((a ^ b) & -(a < b)) ; int r = c ^ ((c ^ temp) & -(c < temp)); return r; } int main(void) { unsigned int a = 3, b = 1, c = 9; printf("%d", getMax(a,b,c)); return 0; } 

Edit: si vous n'êtes pas autorisé à utiliser "<", utilisez la deuxième version

 x - ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1))); 

et gardez à l'esprit l'extrait suivant

Notez que la spécification ANSI C de 1989 ne spécifie pas le résultat du changement de droite signé, ils ne sont donc pas portables. Si des exceptions sont générées lors de débordements, les valeurs de x et y doivent être non signées ou converties en non signées pour les soustractions afin d'éviter de générer inutilement une exception. Toutefois, le décalage à droite nécessite un opérande signé pour produire tous les bits lorsqu'ils sont négatifs. signer là


Edit II: cela devrait fonctionner avec les spécifications que vous avez publiées:

 #include  int getMax(int x, int y, int z) { int r = (x + ~((x+~y+1) & ((x+~y+1) >> 31))+1); // if possible use sizeof(int)*sizeof(char)+~0 instead of 31 int r2 = (z + ~((z+~r+1) & ((z+~r+1) >> 31))+1); // if possible use sizeof(int)*sizeof(char)+~0 instead of 31 return r2; } int main(void) { unsigned int a = 5, b = 7, c = 1; printf("%d", getMax(a,b,c)); return 0; } 

Notez qu'il serait préférable d'utiliser sizeof () au lieu de supposer qu'un int est de 4 octets (ce n'est pas vrai sur toutes les plateformes).

Si vous êtes autorisé à utiliser - (vous suggérez + ), je suggère ce qui suit (non testé) ce qui est, à mon avis, plus efficace que la page de twiddling, en particulier si le premier maximum est une macro, et nous soaps que nous avons affaire à Ints.

 #define MAX2(a,b) (a-((ab) >> (sizeof(int) * CHAR_BIT - 1))*(ba)) int max3 (int x, int y, int z) { return MAX2(MAX2(x, y), z); } 

CHAR_BIT devrait être #define ‘à 8 sur la plupart des plateformes.

Cela repose également sur le comportement indéfini des décalages à droite des nombres négatifs.

Si vous n’êtes pas autorisé à utiliser - , utilisez ~ et ajoutez 1.

La réponse de David Kernin est cependant plus générale.