Comment puis-je en moyenne sécurité deux ints non signés en C ++?

Question

À l'aide de math entier à lui seul, que je voudrais en "toute sécurité" moyenne deux entiers non signés en C++.

Ce que je veux dire par "en toute sécurité" est d'éviter les débordements (et tout ce qui peut être pensé).

Par exemple, le calcul de la moyenne 200 et 5000 est facile:

unsigned int a = 200;
unsigned int b = 5000;
unsigned int moyenne = (a + b) / 2; // Équivaut à: 2600 comme prévu

Mais dans le cas de 4294967295 et 5000 alors:

unsigned int a = 4294967295;
unsigned int b = 5000;
unsigned int moyenne = (a + b) / 2; // Équivaut à: 2499 au lieu de 2147486147

Le meilleur que j'ai trouvé est:

unsigned int a = 4294967295;
unsigned int b = 5000;
unsigned int moyenne = (a / 2) + (b / 2); // Équivaut à: 2147486147 comme prévu

Sont t-il de meilleures façons de faire?

Answer 1

Votre dernière approche semble prometteuse. Vous pouvez améliorer cela en considérant manuellement les bits les plus bas de a et b:

 unsigned int average = (a / 2) + (b / 2) + (a & b & 1);
 

Cela donne les résultats corrects au cas où a et b sont tous les deux impairs.

Answer 2

 unsigned int average = low + ((high - low) / 2);
 

MODIFIER

Voici un article connexe: http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

Answer 3

Votre méthode n’est pas correcte si les deux nombres sont impairs, par exemple 5 et 7, la moyenne est 6 mais votre méthode n ° 3 renvoie 5.

Essaye ça:

 average = (a>>1) + (b>>1) + (a & b & 1)
 

avec des opérateurs mathématiques uniquement:

 average = a/2 + b/2 + (a%2) * (b%2)
 

Answer 4

Si un petit assemblage en ligne x86 ne vous dérange pas, vous pouvez le faire en trois étapes:

 unsigned average(unsigned x, unsigned y)
{
    asm("mov 8(%ebp), %eax");
    asm("add 12(%ebp), %eax");
    asm("rcr %eax");
}
 

Answer 5

Ce que vous avez est bien, avec le détail mineur qui prétend que la moyenne de 3 et 3 est égale à 2. Je suppose que vous ne voulez pas cela; heureusement, il y a une solution facile:

 unsigned int average = a/2 + b/2 + (a & b & 1);
 

Cela vient simplement écraser la moyenne dans le cas où les deux divisions ont été tronquées.