Wie kann ich sicher durchschnittlich zwei unsigned ints in C ++?

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

  •  26-09-2019
  •  | 
  •  

Frage

integer Mit Mathe allein, ich mag "sicher" durchschnittlich zwei unsigned ints in C ++.

Was ich damit meine „sicher“ ist die Vermeidung von überläuft (und alles, was gedacht werden kann).

Zum Beispiel Lungs 200 und 5000 ist einfach: 

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

Aber im Fall von 4294967295 und 5000 dann: 

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

Das Beste, was ich habe kommen mit 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?

War es hilfreich?

Lösung

Ihr letzter Ansatz scheint vielversprechend. Sie können manuell auf das verbessern, indem die niedrigsten Bits von a und b unter Berücksichtigung: 

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

Dies gibt die korrekten Ergebnisse in Fall a und b sind ungerade.

Andere Tipps

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

Bearbeiten

Hier ist ein verwandter Artikel: http : //googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

Ihre Methode ist nicht korrekt, wenn beide Zahlen ungerade sind zB 5 und 7, durchschnittlich 6 aber Ihre Methode # 3 ergibt 5.

Versuchen Sie diese: 

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

mit mathematischen Operatoren nur: 

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

Wenn Sie nicht ein wenig x86 Inline-Assembler (GNU C-Syntax) nichts dagegen haben, können Sie die Vorteile von supercat Vorschlag zur Verwendung nehmen drehen-mit-carry nach einem Add setzen die hohen 32 Bits des vollen 33-Bit-Ergebnis in ein Register

Natürlich können Sie in der Regel sollte Geist Inline-asm verwenden, weil es einige Optimierungen besiegt ( https://gcc.gnu.org/wiki/DontUseInlineAsm ). Aber hier gehen wir auf jeden Fall: 

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

Die % Modifikator dem Compiler mitzuteilen, die args kommutativ nicht tatsächlich dazu beitragen, in dem Fall besser asm ich versuchte, den Aufruf der Funktion mit y eine konstante oder zeiger deref (Speicheroperand) ist. Wahrscheinlich mit einer passenden Einschränkung für ein Ausgangsoperand Niederlage, die, da Sie sie nicht mit Lese-Schreib-Operanden verwenden können.

Wie Sie a href sehen <= "http://gcc.godbolt.org/#z:OYLghAFBqd5QCxAYwPYBMCmBRdBLAF1QCcAaPECAKxAEZTUAHAvVAOwGdK0BbRvADaYA8mwDCCAIZtgmEAHIADPICUpDqgCuxZHPkBSRQEF9AJgDMWAGZ42mANQI8wBPfu1aAVUMmL12w4CqADubu4e3sYA9FH2BE4c9pgAHozEmBwcrGz2eInA6ZIEpPYARpoE9uwCAJ72wSQA1olWJPaanM526LlW9Q6NbCFxCA4kWMQ%2BMbmVDcTN9q3E9lnA3UmEo8vBknUQKbrMK12YPagAbpjEVkGhee1s/uulmFLnrNol0j3xRWDyiUYqEyeFKQhUPg6q3WtkqHFGAnQ7Hs%2BnMABF7LcUaYAEL2RDOVwAWkxIRU9lipgh5hxPkhnTWp3sknOwAA%2BhxMAIBKDCAAvTAQKEnHqSErCxk9Urk/QAdlpxjc6QI2hyEEkFPsVOxeIgpU12rMuo1ZgAbGVsebaNSFSZZWi6dFYgA5YQAFXsAGUjAAxbAlap1OYLPB9Jwo8zYVEYoIAOnp0KZLPZ8K5SLYQoZ6yc4qzTKCMvlPiVmBVxByQR1%2BIg4ZJBYNNrp9sdJid9SaLTapoALETSoRSTJmYlglyBFUcskABymok9r6PexIjJsf6VLCMTCL5HISTc2zAexoNiXNgsdgJkXMy7ESSyTOJnrJXOP%2Bw1CHGOW2sIPV/pDiaAIBCot%2BYSSBwPAQGYpiSOgPRuGYACs%2BiITiyQoWiJRIShOL/hhKFiGwBHAaYpjFj%2BYTQToywIaYyGoXhiEOqR5EUfYIAogxGQYdiZHopMpH4v % 2BgEEOSbjTFoBCMBUHCsRRHE4TUPHQUhijQRA74lBSsS2NJBAcbYIwOBwkg8A46SHuB9jCUBiSSXpsZuGIqA8DwFRFHglz1Js9h2MklRMFc3xyWxOHoUxvHEGZ6nJGJ 0y6RUHEWSUZk8AGyx4K5px4EUmAhWEHFsUV2m% 2BagR5BKULzEBwjn4tByDINBuSJJljA8sgA7ItOpofkYP6NoqYTKqq1kZCJIFNg6n7TUYErrEEQ4skFsg9g% 2BV4LYez6 / ut7CHu% 2BTagW4c35rto0AUBE2DW44GQdBsHwdi9FoRhWF0ThjEOohhHESpV0UVRyA0Y973cUxv19UVClcbJEUqfxTUQDZolhBJFR6bJf0 / lDOJKbDLF0WppEaWo4k6WwekGTk8TGaZ5mYJZiRI3ZaMVLVzmue5LBecEPl% 2BQFm63o8% 2BU / mFymkVFeVE7FpO5OTiWjcAKWYGlVQZVl% 2BC5cL7HFUV0xDOVqCVVcNVuFBpENU19yte1nWTjOvX9ZdEMlmWORI07cpTa2RjxVTowkDUJS8G5BAeV5PjnKgeCiqybKpUwbLAKgGBrZK9hbcdPQAFTviiRaDTnEYYktt73jnJSxR7zYzb79hpJIyAsLoJTxPcmicok0hJP5t72AAssIABqIFGY9S7R6u8hwpgytxGVbwOOmDjSDUrdDkQcSSI0y / oOc0ih7IVR9MHnOeYQSnGJH0fXuy8eMGypSwan6wZ3m2e51% 2B5GF9G17LYKW05wGnaL2LZfY8jsMOHg9gzLSESNTI8Ll% 2BBCGWLuSe / MWA8DwAKGYzIdiBymLEcolQiiYkwOBSordO7EEPOMK4pCCBwNGAgzgoczxlGXjkTKZkNYEDGALb4iw2hGDRF7TON82THg4AQROyd0DPyZNLT% 2Bg1hrll / qXQUtALDdgrkAz2LZLxp2TBI9gUiH5PzEYo / OEMVE5BLnef% 2BJRNHmG7Lo% 2B0qhSACAUIheQpA2AKFoD41ACgxBGiNCsLQOgHBmHMAE0g% 2BklCqDUI0EA5gpyxlMLQAAnFkxQPYMlTnMKaegnj5Ddh8X4hJDAFA% 2BK4IoOJChlBqDgLAJAvAkFXHINwRBggrggGAKaUwpAbBA WNpQUoDSfHBy3AQUQtQJmkHwOkRunkMgTLUEwc8nAFBEmSMgewRIADqe5xyHJSAQXuRJhDmDcESHgkgdAIGjFIDgo5uTuJKd43x8ygkGAsLQby8R04zjnN2ewwAGr2FNOknx8TGlJJAKYNJ3ZuyyhRaaRQphkUFNyR4hQZSvmVJ% 2BTUkAdTYXuOaYgFA3TkGdIgG0npxAUACGkMAcwmS6nDN4dVMZ8yplnlmTUeZizMDLMuFwBJ6zmDZHFTsvZhzjn7IOWci5Vybl3IeU88CryBDvK8eU75Chon / J5oC7qILyosvsOYWMmTYzKHqRK% 2BF5hrXOtdW691uLSn6sJdU9QJKHVws9aYb19qiUBsSaQG8WR2AgG7EAA“rel = "nofollow noreferrer"> auf dem Godbolt Compiler Explorer Dies kompiliert richtig, und so auch eine Version, wo wir die Operanden zu unsigned long ändern, mit dem gleichen Inline-asm. clang3.9 macht ein Chaos von ihm, aber, und beschließt, die "m" Option für die "rme" Einschränkung zu verwenden, so dass es in dem Speicher speichert und verwendet einen Speicheroperanden.

RCR-by-one ist nicht zu langsam, aber es ist immer noch 3 Uops auf Skylake, mit 2-Takt-Latenz. Es ist Great auf AMD CPUs, in dem RCR Einzelzykluslatenz aufweist. (Quelle: Agner Fog Anweisung Tabellen , siehe auch die Tag Wiki für x86-Performance Links). Es ist immer noch besser als @ sellibitze-Version, aber schlechter als @ Sheldons auftragsabhängige Version. (Siehe Code auf Godbolt)

Aber denken Sie daran, dass die Inline-asm Niederlagen Optimierungen wie Konstant-Ausbreitung, so dass jeder rein C ++ Version besser in diesem Fall sein wird.

Und die richtige Antwort ist ... 

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

Was Sie haben, ist in Ordnung, mit dem kleinen Detail, dass es, dass der Durchschnitt von Anspruch 3 wird und 3 2. Ich vermute, dass Sie nicht wollen, dass; Glücklicherweise gibt es eine einfache Lösung: 

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

Diese Bumps nur den Durchschnitt zurück in dem Fall auf, dass beide Divisionen abgeschnitten wurden.

Wenn der Code für ein eingebettetes Mikro, und wenn die Geschwindigkeit kritisch ist, Assembler-Sprache hilfreich sein kann. Auf vielen Mikrocontrollern, geht das Ergebnis des Add natürlich in den Carry-Flag würde und Anweisungen existieren sie in ein Register verschieben zurück. Auf einer ARM, den durchschnittlichen Betrieb (Quelle und dest in den Registern.) In zwei Befehlen durchgeführt werden könnte; jede C-Sprache äquivalent würde mindestens 5 wahrscheinlich ergeben, und wahrscheinlich ein gutes Stück mehr als das.

Im Übrigen auf Maschinen mit kürzeren Wortgrößen, können die Unterschiede noch deutlicher sein. Auf einer 8-Bit-PIC-18-Serie, Mittelungs zwei 32-Bit-Zahlen würden zwölf Anweisungen nehmen. Dadurch könne die Verschiebungen, Hinzufügen und Korrektur, 5 Anweisungen für jede Verschiebung, acht für das Add, und acht für die Korrektur, so 26 (nicht ganz 2.5x Unterschied, aber wahrscheinlich an Bedeutung in absoluten Zahlen) nehmen würde.

(((a&b << 1) + (a^b)) >> 1) ist auch eine nette Art und Weise.

Mit freundlicher Genehmigung: 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;
    }

erwartet durchschnittl == 5.0 für diesen Test

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top