كيف يمكنني بأمان متوسط اثنين غير موقعة رجات في C++?

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

  •  26-09-2019
  •  | 
  •  

سؤال

باستخدام عدد صحيح الرياضيات وحدها ، أود أن "بأمان" متوسط اثنين غير موقعة رجات في C++.

ما أعنيه "بأمان" هو تجنب الفيضانات (وأي شيء آخر يمكن أن يكون الفكر).

على سبيل المثال ، حيث بلغ متوسطها 200 و 5000 هو سهل:

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

ولكن في حالة 4294967295 و 5000 ثم:

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

أفضل جئت به هو:

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

هل هناك أفضل الطرق ؟

هل كانت مفيدة؟

المحلول

آخر النهج يبدو واعدا.يمكنك تحسين ذلك عن طريق يدويا النظر في بت أقل من a و b:

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

وهذا يعطي نتائج صحيحة في حالة كل من a و b هي غريبة.

نصائح أخرى

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

تحرير

هنا هو المادة ذات الصلة: http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

طريقة غير صحيحة إذا كان كل الأرقام الفردية على سبيل المثال 5 و 7 ، متوسط 6 ولكن الأسلوب #3 عوائد 5.

جرب هذا:

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

مع مشغلي الرياضيات فقط:

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

إذا كنت لا تمانع قليلا x86 مضمنة الجمعية العامة (GNU C الجملة) ، يمكنك الاستفادة من supercat اقتراح استخدام تدوير-مع حمل بعد إضافة لوضع عالية 32 بت كامل 33 بت يؤدي إلى تسجيل.

بالطبع, كنت عادة يجب أن العقل باستخدام مضمنة asm, لأنه ينفي بعض التحسينات (https://gcc.gnu.org/wiki/DontUseInlineAsm).ولكن ها نحن على أي حال:

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

على % التعديل أقول مترجم على وسائط هي تبادلي في الواقع لا تساعد على جعل أفضل asm في حالة حاولت استدعاء الدالة مع y كونها ثابتة أو مؤشر deref الذاكرة (المعامل).ربما باستخدام مطابقة القيد لإخراج المعامل الهزائم أنه منذ كنت لا يمكن استخدامه مع قراءة-كتابة المعاملات.

كما ترون على Godbolt مترجم explorer, هذا برمجيا بشكل صحيح, و كذلك نسخة إلى أين نحن تغيير المعاملات إلى unsigned long, مع نفس مضمنة asm.clang3.9 يجعل من الفوضى ، على الرغم من يقرر استخدام "m" الخيار "rme" القيد لذا فإنه يخزن في الذاكرة يستخدم الذاكرة المعامل.

RCR-من قبل-واحدة ليست بطيئة جدا, لكنه لا يزال 3 الجزائرية ، uops على Skylake مع 2 دورة الكمون.انها كبيرة على وحدات المعالجة المركزية AMD, حيث RCR لديه واحدة-دورة الكمون.(المصدر: Agner الضباب تعليمات الجداول, انظر أيضا الوسم ويكي ل x86 الأداء الروابط).فإنه لا يزال أفضل من @sellibitze نسخة ، ولكن أسوأ من @شيلدون هذا النظام تعتمد على الإصدار.(انظر قانون Godbolt)

ولكن تذكر أن مضمنة asm الهزائم التحسينات مثل ثابت الانتشار, لذلك أي pure-C++ الإصدار سيكون أفضل في هذه الحالة.

و الجواب الصحيح هو...

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

ما عليك بخير مع التفاصيل الصغيرة التي سوف يدعون أن متوسط 3 3 2.أظن أنك لا تريد ذلك ؛ لحسن الحظ هناك حل سهل:

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

هذا فقط المطبات متوسط احتياطية في حال كل الشعب اقتطاع.

إذا كان رمز هو جزءا لا يتجزأ من مايكرو و إذا كانت السرعة هي الحاسمة, لغة التجميع قد تكون مفيدة.على العديد من ميكروكنترولر, نتيجة إضافة بطبيعة الحال الذهاب إلى تحمل العلم ، والتعليمات موجودة على التحول مرة أخرى إلى السجل.على ذراع متوسط العملية (المصدر دست.في سجلات) يمكن أن يكون في التعليمات ؛ أي ج-ما يعادل لغة المرجح أن العائد لا يقل عن 5 ، وربما عادلة قليلا أكثر من ذلك.

بالمناسبة ، على الأجهزة مع أقصر كلمة الأحجام الاختلافات يمكن أن تكون حتى أكثر جوهرية.على 8 بت الموافقة المسبقة عن علم-18 سلسلة ، حيث بلغ متوسطها اثنين من أرقام 32 بت يأخذ اثني عشر التعليمات.بفعل التحولات, إضافة, وتصحيح, سيستغرق 5 تعليمات لكل التحول ، ثمانية من أجل إضافة وثمانية التصحيح ، حتى 26 (ليس تماما 2.5 × الفرق ، ولكن ربما أكثر أهمية من حيث القيمة المطلقة).

(((a&b << 1) + (a^b)) >> 1) هو أيضا طريقة لطيفة.

المجاملة: 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;
    }

وتتوقع avg == 5.0 لهذا الاختبار

مرخصة بموجب: CC-BY-SA مع الإسناد
لا تنتمي إلى StackOverflow
scroll top