Wie kann ich sicher Durchschnitt zweier unsigned ints in C++?

Unter Verwendung der integer-Mathematik allein, ich würde gerne "sicher" Durchschnitt zweier unsigned ints in C++.

Was ich meine "sicher" ist die Vermeidung von overflows (und alles andere, was gedacht werden kann).

Zum Beispiel, im Durchschnitt 200 und 5000 leicht:

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

Aber im Falle von 4294967295 und 5000, dann:

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

die beste, Die ich mir ausgedacht habe ist:

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

Gibt es bessere Möglichkeiten?

Kann nicht, die du wirkst, die Summe zu long long?
Die Dritte option wird die falsche Antwort geben, wenn beide a und b sind ungerade, da es Runde, die sich beide Hälften).
US-patent mit der Nummer 6,007,232. Die Berechnung der Mittelwert von zwei integer-zahlen, die gerundet in Richtung null in einer einzigen Instruktion-Zyklus: google.com/patents?id=eAIYAAAAEBAJ&dq=6007232 im wesentlichen verwendet return (a >> 1) + (b >> 1) + (a & b & 0x1);
...wow. Ich bin speichern, der link für das nächste mal, wenn jemand beschwert sich über software-Patente.
es ist interessant, wie viele Antworten enthalten diese patentierte Lösung. Ich bin sicher, dass die meisten/alle von Ihnen entwickelten es selbständig, vielleicht sogar auf der Stelle für Ihre Antwort. Das würde scheinen, zu zeigen das patent nicht erfüllen die Norm der nicht-Offensichtlichkeit.
dies ist ein hardware-patent (beachten Sie, dass das Ergebnis produziert wird in einem Taktzyklus)
Ich bin mir nicht sicher, das ist eine echte Auszeichnung. Der code @ArunSaha schrieb wird die CPU geworden, die Schaltung im patent beschriebene. Es kann sogar Arbeit in einem instruction-Zyklus auf einem modernen x86, aber ich bin mir nicht sicher. Unabhängig davon, daß C++ - code könnte trivial geändert in den VHDL-code, und dann ist es hardware...
York: sagen Sie, ops Antwort nicht funktioniert? er weiß. Wenn Ihr reden ArunSaha Kommentar oder sellibitze beantworten, dann haben Sie vergessen, die + (a & b & 0x1) Teil.

InformationsquelleAutor Tim | 2010-09-28

c++math unsigned-integer x86

49

Ihre Letzte Ansatz scheint vielversprechend. Sie können verbessern, indem manuell in den niedrigsten bits von a und b:
```
unsigned int average = (a / 2) + (b / 2) + (a & b & 1);
```
Dieser gibt die richtigen Ergebnisse in den Fall, dass beide a und b sind ungerade.
- s/agerage/Durchschnitt/g
- Genial, das ist genau die Art von überlegung, die ich suchte.
- Apropos software-Patente scheint es, dass die Patentanmeldung: 20090249356 versucht zu patentieren, was ist bekannt folklore in der computer-Industrie. CAS-weniger einzigen Hersteller einzelne Verbraucher kreisförmigen Warteschlangen bekannt seit fast 30 Jahren. (Schrieb ich meine erste in den frühen 80 ' s), die ich schrieb, um sich zu beschweren, aber Sie sagte, es war zu spät. Ich denke, dass das Patentamt soll überschwemmt werden mit "technischen Hass-E-Mails" auf diese ein.
- Es gibt ein kleines problem mit der Verwendung dieses ein: Samsung hat ein patent für es. google.com/patents?id=eAIYAAAAEBAJ&dq=6007232
- Funktioniert nur für positive ganze zahlen als den letzten Teil ignoriert das Vorzeichen-bit.
InformationsquelleAutor sellibitze
27
```
unsigned int average = low + ((high - low) / 2);
```
BEARBEITEN

Hier ist eine Verwandte Artikel: http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
- ich mag das, aber was, wenn es ein Fehler ist, aufgrund von integer-division?
- Warum würde es sein? Du bist nie der Division durch 0, was ist das nur integer-division, das würde einen Fehler erzeugen.
- Dies ist die klassische Antwort auf dieses problem, vor allem, wenn Sie bereits wissen, welcher Wert hoch und welcher niedrig ist - die Wahl einen Mittelpunkt, zum Beispiel.
- bestellen Sie zu teuer werden würde
- es sei denn, Sie wissen, die Bestellung von a priori, wie im verlinkten Artikel (was wohl der häufigste Anwendungsfall für integer-Mittelung).
- nicht wirklich. während technisch es ein bug ist, es ist fast unmöglich, tatsächlich in eine binäre Suche. Ich bin mir sicher, dass in diesem besonderen Fall war es durchaus üblich, für die Summe bis zum überlauf.
- nicht wirklich. Vielleicht war es fast unmöglich, vor zehn Jahren, aber nicht heute.
- falsch! das ursprüngliche problem wurde über den überlauf. in diesem Fall erlauben Sie high - low unterzeichnet werden, so kann dies leicht overlow in der gleichen Weise wie das ursprüngliche problem. Sie können dies vermeiden, nur durch die Berücksichtigung dieser Unterschied nicht, so müssen Sie wissen, welches größer ist.
- wieder falsch 🙂 bei den meisten Maschinen die Standard-Größe von int ist die gleiche wie die Größe des Zeigers, so dass Sie benötigen eine spezielle Maschine für diese Art von überlauf, mit riesigen Adressraum und kleine ints.
- Nein, Sie wurden unter Bezugnahme auf Java-code, in dem die Größe der int werden immer noch 32 bit. Bitte Lesen Sie den Artikel sorgfältig durch, bevor Sie starke Bemerkungen über Sie.
- Dies ist sehr effizient, wenn Sie bereits wissen, welches höher ist, weniger / schneller asm-Anweisungen als die top-Antwort. Vor allem auf nicht-ARM, wo rechts verschiebt Kosten sind nicht gratis als Teil von anderen Anweisungen. godbolt.org/g/bSZHdE hat asm Ausgabe für x86-und ARM-für beide Versionen.
InformationsquelleAutor Sheldon L. Cooper
17

Ihre Methode ist nicht korrekt, wenn beide zahlen sind ungerade zB 5 und 7, der Durchschnitt ist 6, aber Ihre Methode #3 gibt 5.

Versuchen Sie dies:
```
average = (a>>1) + (b>>1) + (a & b & 1)
```
mit mathematischen Operatoren nur:
```
average = a/2 + b/2 + (a%2) * (b%2)
```
- Müssen Sie fügen Sie ein paar Klammern um Ihre Schichten; andernfalls, was Sie bekommen, ist: (a >> (1 + b) >> (1 + a)) & b & 1. (Dein zweites Beispiel ist richtig, jedoch).
- Behoben, danke 🙂
- +1 für shift statt der division.
- jeder vernünftige compiler optimieren wird, division durch zwei in einer Verschiebung sowieso.
- Von Ihnen positiv bewertet werden für awesomeness!
- hat samsung selbst ein patent auf das zweite zu?
InformationsquelleAutor iniju
9

Wenn Sie don T Geist ein wenig x86 inline Assembler (GNU C-syntax), können Sie die Vorteile der supercat ' s Vorschlag, drehen-mit-carry nach add zu setzen die hohen 32-bits des vollständigen 33-bit-Ergebnis in ein register.

Natürlich, Sie in der Regel sollte dagegen, mit inline-asm, weil es Niederlagen, einige Optimierungen (https://gcc.gnu.org/wiki/DontUseInlineAsm). Aber hier gehen wir sowieso:
```
//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;
}
```
Den die % - Modifikator, um dem compiler die Argumente sind im kommutativen nicht wirklich helfen, bessere asm in der Fall ich habe versucht, den Aufruf der Funktion mit y als eine Konstante oder pointer-deref (memory-operand). Vermutlich mit einem passenden constraint für ein output-operand Niederlagen, da kann man es nicht verwenden, die Lesen und schreiben von Operanden.

Wie Sie sehen können auf der Godbolt compiler explorer, diese korrekt kompiliert, und hat so eine version, wo wir ändern Sie den Operanden zu unsigned long mit den gleichen inline-asm. clang3.9 macht ein Chaos, obwohl, und entscheidet sich für die "m" option für die "rme" Einschränkung, so speichert es im Speicher und verwendet ein Speicher-operand.

RCR-by-one ist nicht zu langsam, aber es ist immer noch 3 uops auf Skylake, mit 2-Takt-Latenz. Es ist toll, auf AMD-CPUs, wo RCR verfügt über Einzel-Zyklus-Latenz. (Quelle: Agner Fog-Anweisung Tabellen, siehe auch die x86 - Tags, wiki für x86-performance-links). Es ist immer noch besser als @sellibitze version, aber schlimmer als @Sheldon ' s um-abhängige version. (Siehe code auf Godbolt)

Aber denken Sie daran, dass inline-asm Niederlagen Optimierungen wie constant-propagation, also alle reinen C++ - version wird besser sein in diesem Fall.
- +1: ich habe nie geschrieben, inline-Montage :(, kannst du bitte Kommentar, und erklären Sie die drei Linien, speziell, wie die Werte x und y abgeholt werden.
- Ich würde auch zu gerne wissen, wie das funktioniert
- Zu Beginn der inline-Montage, es sind vier 4-byte-Werte auf dem stack, beginnend bei EBP: EBP+0 (die vorherigen EBP, vor dem Aufruf der Funktion), EBP+4 (die Vorherige Anweisung counter EIP), EBP+8 (x), und EBP+12 (y). Die Funktion wird erwartet, dass Ihr Ergebnis in EAX, also das beginnt mit der Montage durch verschieben von x gibt. Es fügt dann ein y-und ein überlauf aus diesem Vorgang wird das carry-bit (Mangel an einem überlauf wird deutlich, das bit). RCR ist ein drehen-rechts-mit-tragen, die dreht EAX ein bit nach rechts (Division durch zwei) und schiebt das carry-bit in den meisten beachtlichen bit von EAX.
- Verweis: cse.nd.edu/~dthain/courses/cse40243/fall2008/ia32-intro.html (unter "Definieren von Funktionen"). Auch die Aufrufkonvention verwendet wird cdecl (Standard für C-und nicht-Mitglied C++ - Funktionen), die Sie vielleicht nachschlagen möchten, wenn Sie mehr Informationen wünschen.
- Der Zusatz lässt carry-bit gesetzt, wenn überlauf Auftritt (und man ein wenig mehr ist notwendig, um das Ergebnis aufzunehmen). Dann sind Sie rotieren durch carry rechts (wodurch eax und carry-flag effektiv 33-bit-register), die effektiv teilt sich durch 2. Dann werfen Sie carry-flag (die jetzt enthält die ursprüngliche niedrigsten Mantisse bit von eax) und zurück, eax als das Ergebnis. Genial.
- Es gibt keine solche Sache wie ein overflow in der unsigned-Arithmetik, ist es als tragen (daher der name carry-flag).
- Dieser ist nicht gültig, inline-Montage, da es keine code-Operanden Abhängigkeit. Ein compiler kann optimieren oder Zugriff auf falsche Daten, wenn Sie ruft die Funktion inlined.
- kann Man nicht einfach schreiben, GNU C, basic, asm innerhalb einer Funktion verlassen und ein Wert in %eax. Soweit das der compiler betrifft, die Sie gerade geschrieben haben eine Funktion, die erreicht Ende einer nicht-void-Funktion ohne Rückgabe eines Wertes. Nicht, dass, sobald Sie aktivieren, Optimierung, und vielleicht sogar davor. Verwenden Sie immer die erweiterte asm-syntax mit input-und output-Operanden. (Siehe inline-assembly-tag-wiki). Und, wie R. sagt, natürlich alle drei asm-Anweisungen sollten die gleichen asm-Anweisung.
- Bitte fühlen Sie sich frei, um meine Antwort, Sie haben meinen Segen!
- xD, soll kommentiert haben, ich war gerade dabei, einen zu Bearbeiten. Mir war fast fertig, als du gepostet hast. Und \@fredoverflow: dort gehen Sie, eine version, die in etwa so frei von suckage wie möglich für die inline-asm. Ich würde trotzdem nicht generell empfehlen, aber. Es ist normalerweise am besten, wenn compiler "verstehen", was passiert, damit Sie beweisen können, dass Sie mehr über die Werte von Variablen.
- Naja, insgesamt denke ich, dass deine Bearbeitung besser, aber für meine Referenz Bearbeiten, gibt ein Beispiel, wie man mit Hilfe des kommutativ-Modifizierer hier.
- Auch die output-operand ist nicht early clobber, wie alle Eingangs-Operanden konsumiert an den start. (zB. add %eax, %eax; rcr %eax gültig).
- gute Punkte. Ich habe versucht, Ihr kommutativ Idee, aber es ändert nichts an der asm. Wahrscheinlich kann er es nicht tun, weil der matching-Einschränkung mit einem output-operand. Jedenfalls aktualisiert.
- Legen Sie eine Zeile wie x = foo(); bevor die asm-Anweisung, kompilieren für 32-bit und Optimierung mit -O3, und Sie sollten es mit der x bereits in EAX als [y]/[res] Operanden.
- Und anscheinend müssen Sie GCC 4.8 als gut. Keine Ahnung, warum dieser brach in späteren Compilern.
- ahhh, ich war gerade dabei, Sie zu bitten, nehmen Sie einen Blick an godbolt.org/g/WPNxLB (gcc6.2 und clang3.9), da bin ich schläfrig und dachte, ich war etwas fehlt. Aber ja, gcc4.8.5 (godbolt.org/g/QJhyI6) profitiert von %. Aber noch schlimmer ohne ihn: zwei extra-insns statt nur einer.
InformationsquelleAutor fredoverflow
7

Und die richtige Antwort ist...
```
(A&B)+((A^B)>>1)
```
- Dies tut man nicht, haben die patent-Probleme wie oben?
- Ich danke Ihnen sehr.
- Beeindruckend... Wie funktioniert es?!
InformationsquelleAutor Jonathan Olson
4

Was Sie haben, ist in Ordnung, mit der Kleinigkeit, dass es wird behaupten, dass der Durchschnitt von 3 und 3 ist 2. Ich vermute, dass Sie das nicht wollen; glücklicherweise gibt es eine einfache Lösung:
```
unsigned int average = a/2 + b/2 + (a & b & 1);
```
Diese nur Beulen, die Durchschnittliche back-up im Falle, dass beide Bereiche wurden abgeschnitten.

InformationsquelleAutor Stephen Canon
2

Wenn der code für ein integriertes Mikro, und wenn die Geschwindigkeit ist entscheidend, assembly Sprache kann nützlich sein. Auf viele mikrocontroller, der das Ergebnis der Beurteilung würde natürlich gehen Sie in das carry-flag, und Anweisungen existieren, um verschieben Sie Sie zurück in ein register. Auf einem ARM, der Durchschnittliche Betrieb (source und dest. in Register) kann man in zwei Anweisungen; jede C-Sprache entspricht, würde wahrscheinlich Rendite, die mindestens 5, und wohl ein gutes Stück mehr als das.

Übrigens, auf Maschinen mit kürzeren word Größen, die Unterschiede werden noch deutlicher. Auf einem 8-bit-PIC-18-Serie, die durchschnittlich zwei 32-bit-zahlen dauern würde, zwölf Anweisungen. Dabei die Schichten, Beurteilung und Korrektur in Anspruch nehmen würden, 5 Anweisungen für jede Schicht, acht für das hinzufügen und acht für die Korrektur, so 26 (nicht ganz 2,5 x Unterschied, aber wahrscheinlich mehr Bedeutung in absoluten zahlen).

InformationsquelleAutor supercat
-2

(((a&b << 1) + (a^b)) >> 1) ist auch ein schöner Weg.

Courtesy: http://www.ragestorm.net/blogs/?p=29
- Das ist falsch, da kann es zu einem überlauf. Betrachten Sie 8-bit-Ganzzahlen und Sie möchten den Durchschnitt von 0xff und 0x01. Es sollte 0x80, richtig? Berechnung: 0xff&0x01=0x01, 0x01<<1=0x02, 0xff^0x01=0xfe, 0x02+0xfe=0x00 (weil int-Werte sind 8-bit, 1 0x02+0xfe=0x100 verloren gegangen ist), 0x00>>1=0x00. 0x00!=0x80.
- Das ist einfach falsch, weil nicht überlaufen. Es berechnet, dass der Durchschnitt von 3 und 7 ist 8. Es sollte (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;
    }