هل هناك أي بديل لاستخدام % (معامل) في C/C++؟

Question

قرأت في مكان ما ذات مرة أن مشغل المعامل غير فعال على الأجهزة الصغيرة المدمجة مثل وحدات التحكم الدقيقة 8 بت التي لا تحتوي على تعليمات تقسيم الأعداد الصحيحة.ربما يستطيع شخص ما تأكيد ذلك ولكني أعتقد أن الفرق أبطأ بمقدار 5 إلى 10 مرات من عملية تقسيم الأعداد الصحيحة.

هل هناك طريقة أخرى للقيام بذلك بخلاف الاحتفاظ بمتغير العداد وتجاوزه يدويًا إلى 0 عند نقطة التعديل؟

const int FIZZ = 6;
for(int x = 0; x < MAXCOUNT; x++)
{
    if(!(x % FIZZ)) print("Fizz\n"); // slow on some systems
}

ضد:

الطريقة التي أقوم بها حاليًا:

const int FIZZ = 6;
int fizzcount = 1;
for(int x = 1; x < MAXCOUNT; x++)
{
    if(fizzcount >= FIZZ) 
    {
        print("Fizz\n");
        fizzcount = 0;
    }
}

Answer 1

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

ومع ذلك، هناك فرع صغير من نظرية الأعداد مخصص له الحساب وحدات الأمر الذي يتطلب الدراسة إذا كنت تريد حقًا فهم كيفية تحسين عملية المعامل.على سبيل المثال، تعتبر العمليات الحسابية المعيارية مفيدة جدًا للتوليد المربعات السحرية.

لذا، في هذا السياق، إليك أ مظهر منخفض المستوى للغاية في رياضيات المعامل للحصول على مثال لـ x، والذي يجب أن يوضح لك مدى سهولة مقارنته بالقسمة:

---

ربما تكون طريقة أفضل للتفكير في المشكلة هي من حيث قواعد الأرقام وحساب Modulo.على سبيل المثال ، هدفك هو حساب Dow Mod 7 حيث يكون DOW هو تمثيل 16 بت في يوم الأسبوع.يمكنك كتابة هذا على النحو التالي:

 DOW = DOW_HI*256 + DOW_LO

 DOW%7 = (DOW_HI*256 + DOW_LO) % 7
       = ((DOW_HI*256)%7  + (DOW_LO % 7)) %7
       = ((DOW_HI%7 * 256%7)  + (DOW_LO%7)) %7
       = ((DOW_HI%7 * 4)  + (DOW_LO%7)) %7

معبراً عنه بهذه الطريقة ، يمكنك حساب نتيجة Modulo 7 بشكل منفصل للبايتات العالية والمنخفضة.اضرب النتيجة للعالية بمقدار 4 وأضفها إلى المنخفض ثم احسب Modulo 7.

يمكن إجراء حساب MOD 7 لرقم 8 بت بطريقة مماثلة.يمكنك كتابة رقم مكون من 8 بتات بالنظام الثماني كما يلي:

  X = a*64 + b*8 + c

حيث a وb وc عبارة عن أرقام مكونة من 3 بتات.

  X%7 = ((a%7)*(64%7) + (b%7)*(8%7) + c%7) % 7
      = (a%7 + b%7 + c%7) % 7
      = (a + b + c) % 7

منذ 64%7 = 8%7 = 1

وبطبيعة الحال، أ، ب، ج هي

  c = X & 7
  b = (X>>3) & 7
  a = (X>>6) & 7  // (actually, a is only 2-bits).

أكبر قيمة ممكنة ل a+b+c يكون 7+7+3 = 17.لذلك ، ستحتاج إلى خطوة ثمرة أخرى.يمكن كتابة الإصدار C الكامل (غير المختبر) مثل:

unsigned char Mod7Byte(unsigned char X)
{
    X = (X&7) + ((X>>3)&7) + (X>>6);
    X = (X&7) + (X>>3);

    return X==7 ? 0 : X;
}

قضيت بضع لحظات في كتابة نسخة الموافقة المسبقة عن علم.التنفيذ الفعلي يختلف قليلاً عن الموصوف أعلاه

Mod7Byte:
       movwf        temp1        ;
       andlw        7        ;W=c
       movwf        temp2        ;temp2=c
       rlncf   temp1,F        ;
       swapf        temp1,W ;W= a*8+b
       andlw   0x1F
       addwf        temp2,W ;W= a*8+b+c
       movwf        temp2   ;temp2 is now a 6-bit number
       andlw   0x38    ;get the high 3 bits == a'
       xorwf        temp2,F ;temp2 now has the 3 low bits == b'
       rlncf   WREG,F  ;shift the high bits right 4
       swapf   WREG,F  ;
       addwf        temp2,W ;W = a' + b'

 ; at this point, W is between 0 and 10


       addlw        -7
       bc      Mod7Byte_L2
Mod7Byte_L1:
       addlw        7
Mod7Byte_L2:
       return

إليك روتين صغير لاختبار الخوارزمية

       clrf    x
       clrf    count

TestLoop:
       movf        x,W
       RCALL   Mod7Byte
       cpfseq count
        bra    fail

       incf        count,W
       xorlw   7
       skpz
        xorlw        7
       movwf   count

       incfsz        x,F
       bra        TestLoop
passed:

أخيرًا ، بالنسبة للنتيجة 16 بت (التي لم أختبرها) ، يمكنك الكتابة:

uint16 Mod7Word(uint16 X)
{
 return Mod7Byte(Mod7Byte(X & 0xff) + Mod7Byte(X>>8)*4);
}

سكوت

---

Answer 2

إذا كنت تقوم بحساب رقم بطريقة ما، فيمكنك استخدام عامل التشغيل والبت.فقط اطرح واحدًا من الرقم الثاني.على سبيل المثال:

x % 8 == x & 7
x % 256 == x & 255

بعض التحذيرات:

1. هذا يعمل فقط إذا كان الرقم الثاني هو قوة اثنين.
2. إنه مكافئ فقط إذا كان المعامل موجبًا دائمًا.لا تحدد معايير C وC++ إشارة المعامل عندما يكون الرقم الأول سالبًا (حتى C++ 11، والذي يفعل ضمان أنها ستكون سلبية، وهو ما كان يفعله معظم المترجمين بالفعل).من الحكمة بعض الشيء والتخلص من علامة الإشارة، لذلك ستكون دائمًا إيجابية (أي.إنه معامل حقيقي، وليس باقيا).يبدو أن هذا ما تريده على أي حال.
3. ربما يقوم برنامج التحويل البرمجي الخاص بك بذلك بالفعل عندما يتمكن من ذلك، لذلك في معظم الحالات لا يستحق القيام بذلك يدويًا.

Answer 3

هناك حمل عام في معظم الأوقات في استخدام modulo الذي لا يمثل قوى 2.هذا بغض النظر عن المعالج حيث أن (AFAIK) حتى المعالجات ذات معاملات المعاملات تكون أبطأ ببضع دورات في عمليات التقسيم مقارنة بعمليات القناع.

في معظم الحالات، لا يعد هذا تحسينًا يستحق الاهتمام، وبالتأكيد لا يستحق حساب عملية الاختصار الخاصة بك (خاصة إذا كانت لا تزال تتضمن القسمة أو الضرب).

ومع ذلك، هناك قاعدة أساسية تتمثل في تحديد أحجام المصفوفات وما إلى ذلك.أن تكون صلاحيات 2.

لذلك إذا كان حساب يوم الأسبوع ، فقد يستخدم أيضًا ٪ 7 بغض النظر عما إذا كان إنشاء مخزن مؤقت دائري يبلغ حوالي 100 إدخالات ...لماذا لا نجعلها 128يمكنك بعد ذلك كتابة % 128 وسيقوم معظم المترجمين (جميع) بعمل هذا & 0x7F

Answer 4

ما لم تكن بحاجة حقًا إلى أداء عالي على العديد من الأنظمة الأساسية المضمنة، فلا تغير طريقة البرمجة لأسباب تتعلق بالأداء حتى تقوم بإنشاء ملف تعريف!

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

Answer 5

@ماثيو على حق.جرب هذا:

int main() {
  int i;
  for(i = 0; i<=1024; i++) {
    if (!(i & 0xFF)) printf("& i = %d\n", i);
    if (!(i % 0x100)) printf("mod i = %d\n", i);
  }
}

Answer 6

x%y == (x-(x/y)*y)

أتمنى أن يساعدك هذا.

Answer 7

في العالم المدمج ، غالبًا ما تكون عمليات "المعامل" التي تحتاج إلى القيام بها هي تلك التي تنقسم بشكل جيد إلى عمليات بت التي يمكنك القيام بها مع "و" و "|" وأحيانًا ">>".

Answer 8

هل يمكنك الوصول إلى أي جهاز قابل للبرمجة على الجهاز المدمج؟مثل العدادات وهكذا؟إذا كان الأمر كذلك، فقد تتمكن من كتابة وحدة تعديل تعتمد على الأجهزة، بدلاً من استخدام % المحاكى.(لقد فعلت ذلك مرة واحدة في VHDL.لست متأكدًا مما إذا كان لا يزال لدي الرمز بالرغم من ذلك.)

انتبه، لقد قلت أن القسمة كانت أسرع بـ 5 إلى 10 مرات.هل فكرت في إجراء القسمة والضرب والطرح لمحاكاة الوضع؟(يحرر:أسيء فهم المشاركة الأصلية.لقد اعتقدت أنه من الغريب أن يكون القسمة أسرع من التعديل، فهما نفس العملية.)

في حالتك المحددة، على الرغم من ذلك، فإنك تتحقق من وجود تعديل رقم 6.6 = 2*3.لذلك ربما يمكنك الحصول على بعض المكاسب الصغيرة إذا قمت أولاً بالتحقق مما إذا كان البت الأقل أهمية هو 0.شيء مثل:

if((!(x & 1)) && (x % 3))
{
    print("Fizz\n");
}

ومع ذلك، إذا قمت بذلك، فإنني أوصيك بتأكيد حصولك على أي مكاسب، وهذا جيد بالنسبة لمحللي الملفات الشخصية.والقيام ببعض التعليقات.سأشعر بالسوء تجاه الرجل التالي الذي عليه أن ينظر إلى الكود بطريقة أخرى.

Answer 9

يجب عليك حقًا التحقق من الجهاز المدمج الذي تحتاجه.كل لغات التجميع التي رأيتها (x86، 68000) تنفذ المعامل باستخدام القسمة.

في الواقع، تقوم عملية تجميع القسمة بإرجاع نتيجة القسمة والباقي في سجلين مختلفين.

Answer 10

لا يعني ذلك أن هذا أفضل بالضرورة، ولكن يمكن أن يكون لديك حلقة داخلية تصل دائمًا إلى FIZZ، وحلقة خارجية تكرر كل ذلك لعدد معين من المرات.ربما يتعين عليك بعد ذلك وضع حالة خاصة في الخطوات القليلة الأخيرة إذا لم يكن MAXCOUNT قابلاً للقسمة بالتساوي على FIZZ.

ومع ذلك، أقترح إجراء بعض الأبحاث وتحليل الأداء على الأنظمة الأساسية المقصودة للحصول على فكرة واضحة عن قيود الأداء التي تخضع لها.قد تكون هناك أماكن أكثر إنتاجية لبذل جهود التحسين الخاصة بك.

Answer 11

@جيف الخامس:أرى مشكلة في ذلك!(أبعد من ذلك، كان الكود الأصلي الخاص بك يبحث عن mod 6 والآن أنت تبحث بشكل أساسي عن mod 8).استمر في إجراء 1+ إضافي!نأمل أن يقوم برنامج التحويل البرمجي الخاص بك بتحسين ذلك، ولكن لماذا لا يبدأ الاختبار عند 2 فقط وينتقل إلى MAXCOUNT شاملاً؟أخيرًا، ستعود صحيحًا في كل مرة يكون فيها (x+1) غير قابل للقسمة على 8.هل هذا ما تريده؟(أفترض ذلك، ولكن أريد فقط التأكيد).

Answer 12

بالنسبة إلى modulo 6، يمكنك تغيير كود Python إلى C/C++:

def mod6(number):
    while number > 7:
        number = (number >> 3 << 1) + (number & 0x7)
    if number > 5:
        number -= 6
    return number

Answer 13

سوف يستغرق بيان الطباعة وقتًا أطول حتى من أبطأ تنفيذ لمشغل المعامل.لذا فإن التعليق "بطيء في بعض الأنظمة" يجب أن يكون "بطيئًا في جميع الأنظمة".

كما أن مقتطفي الكود المقدمين لا يفعلان نفس الشيء.وفي الثاني الخط

if(fizzcount >= FIZZ)

دائمًا خطأ، لذلك لا تتم طباعة "FIZZ " أبدًا.