Comment puis-je sans risque durée moyenne de deux entiers non signés en C++?

À 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, avec une moyenne de 200 et 5000, c'est simple:

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 puis:

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

Le meilleur que j'ai trouvé est:

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

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

Ne pouvez-vous pas jeté la somme de long long?
La troisième option de donner la mauvaise réponse, si a et b sont impairs (puisqu'il va s'arrondir vers le bas les deux moitiés).
Numéro de brevet AMÉRICAIN 6,007,232. Le calcul de la moyenne de deux nombres entiers arrondi vers zéro en un seul cycle d'instruction: google.com/patents?id=eAIYAAAAEBAJ&dq=6007232 utilise essentiellement return (a >> 1) + (b >> 1) + (a & b & 0x1);
...wow. Je suis sauver ce lien pour la prochaine fois que quelqu'un se plaint à propos des brevets logiciels.
il est intéressant de voir comment beaucoup de réponses ci-dessous contiennent cette solution brevetée. Je suis sûr que la plupart d'entre eux n'a développé de façon indépendante, peut-être même sur place pour leur réponse. Qui semble indiquer que le brevet ne répond pas à la norme de non-évidence.
c'est un matériel des brevets (notez que le résultat est produit en un seul cycle d'horloge)
Je ne suis pas sûr que ce soit une vraie distinction. Le code @ArunSaha a écrit fera le CPU devenir le circuit décrit dans le brevet. Il peut même travailler dans un cycle d'instruction sur un x86, mais je ne suis pas certain. Peu importe, que le code C++ peut être trivialement changé dans le code VHDL, et puis c'est matériel...
York: dites-vous ops réponse ne marche pas? il sait. Si votre parler ArunSaha commentaire ou sellibitze réponse, puis vous avez oublié le + (a & b & 0x1) partie.

InformationsquelleAutor Tim | 2010-09-28

c++math unsigned-integer x86

49

Votre dernière approche semble prometteuse. Vous pouvez améliorer manuellement compte tenu de la plus faible de bits de a et de b:
```
unsigned int average = (a / 2) + (b / 2) + (a & b & 1);
```
Cela donne des résultats corrects dans le cas où a et b sont impairs.
- s/agerage/moyenne/g
- Génial, c'est exactement le genre de considération que je cherchais.
- En parlant de brevets logiciels, il semble que la demande de brevet: 20090249356 est d'essayer de brevet, ce qui est bien connu du folklore dans l'industrie informatique. CAS-moins seul producteur consommateur circulaire files d'attente ont été connus depuis près de 30 ans. (J'ai écrit mon premier au début des années 80), j'ai écrit pour se plaindre, mais ils ont dit que c'était trop tard. Je pense que le bureau des brevets doit être inondé avec des techniques", la haine des mails" sur celui-ci.
- Il y a un léger problème avec l'aide de celui-ci: Samsung a déposé un brevet pour elle. google.com/patents?id=eAIYAAAAEBAJ&dq=6007232
- Ne fonctionne que pour des entiers positifs comme la dernière partie ignore le bit de signe.
InformationsquelleAutor sellibitze
27
```
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
- j'aime bien, mais que faire si il y a une erreur due à la division entière?
- Pourquoi y aurait-il? Vous n'êtes jamais à diviser par 0, qui est la seule division entière qui produirait une erreur.
- C'est la réponse classique à ce problème, surtout si vous savez déjà ce qui est élevé et qui est faible - le choix d'un milieu, par exemple.
- la commande serait trop cher
- sauf si vous savez de la commande a priori, comme dans l'article lié (qui est probablement le plus commun de cas d'utilisation pour l'entier en moyenne).
- pas vraiment. alors que techniquement, c'est un bug, il est presque impossible de réellement se produire dans un système binaire de recherche. Je suis sûr que dans ce cas particulier, il était tout à fait commun pour la somme de débordement.
- pas vraiment. Peut-être qu'il était presque impossible il y a dix ans, mais pas aujourd'hui.
- faux! le problème initial était d'environ débordement. dans ce cas, vous permettent high - low être signé, donc cela peut facilement overlow de la même manière que dans le problème original. vous pouvez l'éviter, seule la prise en compte de cette différence, non signé, de sorte que vous avez à savoir laquelle est la plus grande.
- de nouveau mal 🙂 sur la plupart des machines de la taille par défaut de int est la même que la taille du pointeur, donc il faut une machine spéciale pour ce genre de débordement, avec un énorme espace d'adressage et les petits entiers.
- non, vous faisiez référence à du code Java, dans lequel la taille de int seront toujours en 32 bits. Veuillez lire l'article attentivement avant de prendre une forte remarques à ce sujet.
- C'est très efficace si vous savez déjà lequel est plus élevé, moins de / plus rapide asm instructions que le haut de réponse. En particulier sur la non-BRAS, où le droit des quarts de coût ne sont pas libres dans le cadre d'autres instructions. godbolt.org/g/bSZHdE a l'asm de sortie pour les architectures x86 et ARM pour les deux versions.
InformationsquelleAutor Sheldon L. Cooper
17

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

Essayez ceci:
```
average = (a>>1) + (b>>1) + (a & b & 1)
```
avec les mathématiques seuls opérateurs:
```
average = a/2 + b/2 + (a%2) * (b%2)
```
- Vous avez besoin d'ajouter des parenthèses autour de vos déplacements; sinon, ce que vous obtenez est: (a >> (1 + b) >> (1 + a)) & b & 1. (Votre deuxième exemple est correct, cependant).
- Corrigé, merci 🙂
- +1 pour le changement au lieu de la division.
- toute raisonnable compilateur d'optimiser la division par deux en un changement de toute façon.
- Upvoted pour awesomeness!
- samsung propriétaire d'un brevet sur la seconde de trop?
InformationsquelleAutor iniju
9

Si vous n'avez pas l'esprit un peu x86 assembly en ligne (GNU C syntaxe), vous pouvez profiter de supercat la suggestion d'utiliser tourner-à-porter après un complément de mettre le haut de 32 bits de l'intégralité de 33 bits résultat dans un registre.

Bien sûr, vous avez généralement devrait esprit à l'aide inline-asm, car il va à l'encontre de certaines optimisations (https://gcc.gnu.org/wiki/DontUseInlineAsm). Mais ici nous allons de toute façon:
```
//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;
}
```
La % modificateur pour indiquer au compilateur les arguments sont commutative ne fait pas les aider à mieux asm dans le cas que j'ai essayé, l'appel de la fonction avec y étant une constante ou un pointeur-deref (mémoire opérande). Probablement à l'aide d'une correspondance de contrainte pour une sortie opérande défaites que, puisque vous ne pouvez pas l'utiliser avec d'écriture-lecture des opérandes.

Comme vous pouvez le voir sur le Godbolt compilateur explorer, cette compile correctement, et de ce fait une version où nous changer les opérandes de unsigned long, avec la même asm inline. clang3.9 fait un gâchis, même si, et décide d'utiliser la "m" option pour le "rme" contrainte, de sorte qu'il stocke en mémoire et utilise une mémoire opérande.

RCR-en-un n'est pas trop lent, mais c'est toujours 3 uop sur Skylake, avec 2 cycle de latence. C'est génial sur les Processeurs AMD, où RCR à un seul cycle de latence. (Source: Agner le Brouillard de l'instruction tables, voir aussi le x86 la balise wiki pour x86 performance des liens). C'est toujours mieux que @sellibitze version, mais pire que @Sheldon est dépendant de l'ordre de version. (Voir code sur Godbolt)

Mais n'oubliez pas que inline-asm défaites optimisations comme la constante de propagation, de sorte que toute pure-C++ version sera mieux dans ce cas.
- +1: je n'ai jamais écrit assembly en ligne :(, pouvez-vous commenter et expliquer les trois lignes, spécialement la manière dont les valeurs de x et y sont ramassés.
- J'aimerais également savoir comment cela fonctionne
- Au début de la ligne d'assemblage, il y a quatre 4-valeurs d'octets sur la pile, en commençant à EBP: EBP+0 (le précédent EBP, avant l'appel de fonction), EBP+4 (l'instruction précédente contre l'EIP), EBP+8 (x), et EBP+12 (y). La fonction est prévu pour placer son résultat dans EAX, de sorte que l'assemblée commence par le déplacement x-y. Il ajoute ensuite y, et un débordement de cette opération permettra de définir le bit de retenue (manque de débordement efface le bit). RCR est une rotation vers la droite-à-porter, qui tourne EAX un bit vers la droite (division par deux) et les changements du bit dans le plus sigificant peu de EAX.
- Référence: cse.nd.edu/~dthain/courses/cse40243/fall2008/ia32-intro.html (en vertu de la "Définition des Fonctions"). Aussi, la convention d'appel utilisée est cdecl (la valeur par défaut pour le C et le non-membre de fonctions C++), ce qui, vous voudrez peut-être regarder si vous voulez plus d'informations.
- L'ajout de feuilles de réaliser l'ensemble de peu lors du dépassement de capacité se produit (et un peu plus est nécessaire pour contenir le résultat). Ensuite, vous tournez à travers transporter droite (ce qui eax et le drapeau de portage efficacement 33 bits de registre) qui permet de diviser par 2. Puis vous jetez drapeau de portage (qui contient maintenant original plus bas significande peu de eax) et retour eax comme résultat. Brillant.
- Il n'y a pas une telle chose comme un overflow en arithmétique non signée, elle est appelée porter (d'où le nom de porter le drapeau).
- Ce n'est pas valable assembly en ligne parce qu'il n'a pas de code de l'opérande de dépendance. Un compilateur peut optimiser ou l'accès à des données erronées lorsque la fonction est insérée.
- Vous ne pouvez pas écrire GNU C de base de l'asm à l'intérieur d'une fonction et de laisser une valeur en %eax. Aussi loin que le compilateur est concerné, vous avez juste écrit une fonction qui atteint la fin de non-void function sans retourner une valeur. Qui échoue dès que vous activez l'optimisation, et peut-être même avant. Toujours l'utilisation prolongée-asm syntaxe avec entrée et sortie des opérandes. (Voir le inline assemblée balise wiki). Et comme R. dit, bien sûr, tous les trois instructions asm devrait faire partie de la même asm déclaration.
- N'hésitez pas à améliorer ma réponse, vous avez ma bénédiction!
- xD, devrait avoir commenté, je travaillais sur un montage. Le mien était presque prêt lorsque vous avez posté. Et \@fredoverflow: là vous allez, une version qui est sur le point de suckage que possible en ligne de l'asm. Je n'est généralement pas recommandé, cependant. Il est généralement préférable si compilateur "comprendre" ce qui se passe, de sorte qu'ils peuvent se révéler plus sur les valeurs des variables.
- Ainsi, globalement, je pense que votre montage est mieux, mais mon montage donne un exemple de comment vous pouvez utiliser le commutative modificateur ici.
- Également la sortie de l'opérande n'est pas début de trouvailles, comme tous les opérandes d'entrée consommée au début. (eg. add %eax, %eax; rcr %eax serait valide).
- les bons points. J'ai essayé votre commutative idée, mais on ne change pas l'asm. Probablement, il ne peut pas le faire à cause de la contrainte de correspondance avec un opérande de sortie. De toute façon, mis à jour.
- Mettre une ligne comme x = foo(); avant l'asm déclaration, compiler pour 32-bits, et d'optimiser la avec-O3 et vous devriez le voir à l'aide de la x déjà dans EAX comme le [y]/[res] opérande.
- Et apparemment, vous devez utiliser GCC 4.8 ainsi. Ne sais pas pourquoi, c'est plus tard dans les compilateurs.
- ah, j'allais vous demander de prendre un coup d'oeil à godbolt.org/g/WPNxLB (gcc6.2 et clang3.9), depuis que je suis endormie et compris qu'il me manquait quelque chose. Mais ouais, gcc4.8.5 (godbolt.org/g/QJhyI6) ne bénéficient d' %. Mais encore pire, sans elle: deux insns au lieu d'un seul.
InformationsquelleAutor fredoverflow
7

Et la bonne réponse est...
```
(A&B)+((A^B)>>1)
```
- Celui de ne pas avoir le brevet problèmes ci-dessus?
- Je vous remercie beaucoup.
- Impressionnant... Comment ça fonctionne?!
InformationsquelleAutor Jonathan Olson
4

Ce que vous avez est très bien, avec le petit détail qu'il va prétendre que la moyenne des 3 et 3 est 2. Je devine que vous ne voulez pas que, heureusement, il y a une solution facile:
```
unsigned int average = a/2 + b/2 + (a & b & 1);
```
- Ce juste des bosses de la moyenne dans le cas que les deux divisions ont été tronqués.

InformationsquelleAutor Stephen Canon
2

Si le code est pour un micro intégré, et si la vitesse est critique, langage d'assemblage peuvent être utiles. Sur de nombreux microcontrôleurs, le résultat de l'ajouter naturellement aller dans le porte drapeau, et les instructions existent pour le déplacer de nouveau dans un registre. Sur un BRAS, l'exploitation moyenne (source et dest. dans les registres) peut être effectué de deux instructions; C-équivalent en langue produira probablement au moins 5, et probablement un peu juste plus que cela.

D'ailleurs, sur les machines avec des temps de parole tailles, les différences peuvent être encore plus importants. Sur un 8-bit PIC-18 de la série, avec une moyenne de deux nombres de 32 bits prendrait douze instructions. Faire les changements, d'ajouter et de correction, faudrait 5 instructions pour chaque quart de travail, huit pour l'ajouter, et huit pour la correction, donc 26 (pas assez de 2,5 x différence, mais probablement plus important en termes absolus).

InformationsquelleAutor supercat
-1

De la dernière approche
```
unsigned int average = (a / 2) + (b / 2); //Equals: 2147486147 as expected
```
ne fonctionne pas, parfois, à cause des erreurs d'arrondi.

InformationsquelleAutor Zhaorui Ding
-2

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

Courtoisie: http://www.ragestorm.net/blogs/?p=29
- Ce qui est faux, car il peut y avoir un dépassement de capacité. Envisager de 8 bits ints et vous voulez trouver le moyen de 0xff et 0x01. Il devrait être 0x80, droit? Calcul: 0xff&0x01=0x01, 0x01<<1=0x02, 0xff^0x01=0xfe, 0x02+0xfe=0x00 (parce entiers sur 8 bits, le 1 en 0x02+0xfe=0x100 est perdu), 0x00>>1=0x00. 0x00!=0x80.
- C'est juste mauvais, pas de raison de dépassement de capacité. Il va calculer la moyenne des 3 et 7 est 8. Il devrait être (a&b)+((a^b)>>1).
InformationsquelleAutor shubhros

-2

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

attend avg == 5.0 pour ce test

Votre réponse est mauvaise et vous devriez vous sentir mal.

InformationsquelleAutor Toni Rossmann

Vous devez vous connecter pour publier un commentaire.