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

StackOverflow https://stackoverflow.com/questions/3816446

  •  26-09-2019
  •  | 
  •  

Question

En utilisant seul les mathématiques entier, je voudrais « en toute sécurité » en moyenne deux ints non signés en C ++.

Qu'est-ce que je veux dire par « en toute sécurité » est d'éviter les débordements (et tout ce qui peut être considéré).

Par exemple, la moyenne 200 et 5000 est facile: 

unsigned int a = 200;
unsigned int b = 5000;
unsigned int average = (a + b) / 2; // Equals: 2600 as intended

Mais dans le cas de 4294967295 et 5000 alors: 

unsigned int a = 4294967295;
unsigned int b = 5000;
unsigned int average = (a + b) / 2; // Equals: 2499 instead of 2147486147

Le meilleur que je suis venu avec est: 

unsigned int a = 4294967295;
unsigned int b = 5000;
unsigned int average = (a / 2) + (b / 2); // Equals: 2147486147 as expected

Y at-il de meilleures façons?

Était-ce utile?

La solution

La dernière approche semble prometteuse. Vous pouvez améliorer ce 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 des résultats corrects en cas a et b sont impairs.

Autres conseils

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

EDIT

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

Votre méthode n'est pas correct si les deux chiffres sont par exemple impair 5 et 7, moyenne est de 6, mais votre méthode # 3 renvoie 5.

Essayez ceci: 

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

avec des opérateurs mathématiques seulement: 

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

Si cela ne vous dérange pas un peu x86 assembleur en ligne (syntaxe GNU C), vous pouvez profiter de la suggestion de supercat utiliser https://gcc.gnu.org/wiki/DontUseInlineAsm ). Mais on y va quand même: 

// works for 64-bit long as well on x86-64, and doesn't depend on calling convention
unsigned average(unsigned x, unsigned y)
{
    unsigned result;
    asm("add   %[x], %[res]\n\t"
        "rcr   %[res]"
        : [res] "=r" (result)   // output
        : [y] "%0"(y),  // input: in the same reg as results output.  Commutative with next operand
          [x] "rme"(x)  // input: reg, mem, or immediate
        :               // no clobbers.  ("cc" is implicit on x86)
    );
    return result;
}

Le % modificateur pour indiquer au compilateur les args sont commutative ne fait pas aider à faire mieux asm dans le cas où j'ai essayé, appelant la fonction y étant une constante ou pointeur-deref (opérande de mémoire). Probablement en utilisant une contrainte correspondant pour une sortie opérande défaites que, puisque vous ne pouvez pas l'utiliser avec opérandes lecture-écriture.

Comme vous pouvez le voir sur l'explorateur Godbolt compilateur , correctement cette compile, et le fait d'une version où l'on change les opérandes à unsigned long, avec le même asm en ligne. clang3.9 fait un gâchis de celui-ci, cependant, et décide d'utiliser l'option "m" pour la contrainte de "rme", il stocke en mémoire et utilise une mémoire opérande.

RCR par un pas trop lent, mais il est encore 3 UOP sur Skylake, avec une latence de 2 cycle. Il est grande sur les processeurs AMD, où la latence RCR un seul cycle. (Source: Agner tables d'instruction de brouillard , vous pouvez aussi consulter la pour les liens de performance x86). Il est encore mieux que la version de @ sellibitze, mais pire que la version @ dépendante de l'ordre de Sheldon. (Voir code sur Godbolt)

Mais rappelez-vous que les défaites inline-asm optimisations telles que la propagation constante, de sorte que toute la version pure C sera mieux dans ce cas.

Et la réponse est ... 

(A&B)+((A^B)>>1)

Qu'est-ce que vous avez est très bien, avec le détail mineur qu'il réclamera que la moyenne des 3 et 3 est 2. Je devine que vous ne voulez pas que; Heureusement, il y a une solution simple: 

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

Cette juste bosses l'arrière moyenne dans le cas où les deux divisions ont été tronqués.

Si le code est pour un micro intégré, et si la vitesse est critique, peut être utile langage d'assemblage. Sur de nombreux micro-contrôleurs, le résultat de l'ajout irait naturellement dans le drapeau de transport, et les instructions existent pour le déplacer de nouveau dans un registre. Sur un bras, l'opération moyenne (source et dest dans les registres.) Pourrait être fait en deux instructions; tout équivalent en langage C produirait probablement au moins 5, et probablement un peu juste plus que cela.

Par ailleurs, sur des machines avec des tailles de mots plus courts, les différences peuvent être encore plus importante. Sur un PIC-18 série 8 bits, soit en moyenne deux numéros 32 bits prendrait douze instructions. Faire les quarts de travail, d'ajouter et de correction, prendrait 5 des instructions pour chaque quart de travail, huit pour le complément, et huit pour la correction, donc 26 (pas tout à fait une différence 2,5x, mais probablement plus importante en termes absolus).

(((a&b << 1) + (a^b)) >> 1) est aussi une belle façon.

Avec l'aimable autorisation: http://www.ragestorm.net/blogs/?p=29 

    int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    decimal avg = 0;
    for (int i = 0; i < array.Length; i++){
        avg = (array[i] - avg) / (i+1) + avg;
    }

5.0 == avg attend pour ce test

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top