كيف يمكن لي أن تنفيذ التضمين المنطقي مع أحادي المعامل أو رمز كفاءة آخرين في C؟

Question

وأريد لتنفيذ العملية المنطقية التي تعمل كفاءة قدر الإمكان. أحتاج هذا الجدول الحقيقة:

p    q    p → q
T    T      T
T    F      F
F    T      T
F    F      T

وهذا، وفقا لويكيبيديا يسمى " منطقية ضمنا "

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

والشكر

Answer 1

ولمعلوماتك، مع دول مجلس التعاون الخليجي-4.3.3:

int foo(int a, int b) { return !a || b; }
int bar(int a, int b) { return ~a | b; }

ويعطي (من -d objdump):

0000000000000000 <foo>:
   0:   85 ff                   test   %edi,%edi
   2:   0f 94 c2                sete   %dl
   5:   85 f6                   test   %esi,%esi
   7:   0f 95 c0                setne  %al
   a:   09 d0                   or     %edx,%eax
   c:   83 e0 01                and    $0x1,%eax
   f:   c3                      retq   

0000000000000010 <bar>:
  10:   f7 d7                   not    %edi
  12:   09 fe                   or     %edi,%esi
  14:   89 f0                   mov    %esi,%eax
  16:   c3                      retq   

وهكذا، لا الفروع، ولكن ضعف عدد التعليمات.

وحتى أفضل، مع _Bool (بفضلlitb):

_Bool baz(_Bool a, _Bool b) { return !a || b; }

0000000000000020 <baz>:
  20:   40 84 ff                test   %dil,%dil
  23:   b8 01 00 00 00          mov    $0x1,%eax
  28:   0f 45 c6                cmovne %esi,%eax
  2b:   c3                      retq   

وهكذا، وذلك باستخدام _Bool بدلا من int هو فكرة جيدة.

وبما أنني استكمال اليوم، لقد أكدت دول مجلس التعاون الخليجي 8.2.0 ينتج مماثلة، وإن لم تكن متطابقة، نتائج _Bool:

0000000000000020 <baz>:
  20:   83 f7 01                xor    $0x1,%edi
  23:   89 f8                   mov    %edi,%eax
  25:   09 f0                   or     %esi,%eax
  27:   c3                      retq   

Answer 2

~p | q

لالتصور:

perl -e'printf "%x\n", (~0x1100 | 0x1010) & 0x1111'
1011

في كود ضيق، وهذا ينبغي أن يكون أسرع من "! ص || ف" لأن هذا الأخير لديه فرع، والتي قد تتسبب في كشك في وحدة المعالجة المركزية بسبب خطأ التنبؤ فرع. النسخة المختصة بالبت غير القطعية و، على سبيل المكافأة، ويمكن القيام 32 مرات كما الكثير من العمل في عدد صحيح 32-بت من الإصدار منطقية!

Answer 3

!p || q

وغير الكثير بسرعة. على محمل الجد، لا تقلق بشأن ذلك.

Answer 4

ويمكنك تقرأ على اشتقاق التعبيرات المنطقية من جداول الحقيقة (وأيضا يمكنك الاطلاع على شكل الكنسي )، على الطريقة التي يمكن أن تعبر عن أي جدول الحقيقة كما مزيج من البدائيون منطقية أو وظائف.

Answer 5

وهناك حل آخر لالقيم المنطقية C (قليلا قذرة، ولكن الأعمال):

و((unsigned int)(p) <= (unsigned int)(q))

وكان يعمل منذ وفق المعايير C، 0 يمثل كاذبة، وأية قيمة أخرى حقيقية (يتم إرجاع 1 للصحيح من قبل مشغلي منطقية، نوع int).

وو"قذارة" هي التي تستخدم القيم المنطقية (p وq) أنها أعداد صحيحة، وهو ما يتناقض بعض السياسات الكتابة قوية (مثل ميسرا)، حسنا، هذا هو السؤال الأمثل. تستطيع #define دائما بانها الماكرو لإخفاء الأشياء القذرة.

لp منطقية سليمة وq (وجود إما 0 أو تمثيلات الثنائية 1) يعمل. وإلا قد تفشل T->T لإنتاج T إذا p وq لها قيمة غير صفرية التعسفي لتمثيل صحيح.

إذا كنت بحاجة إلى تخزين النتيجة فقط، لأن بنتيوم II، هناك (نقل الشرطي) تعليمات cmovcc (كما هو مبين في الجواب Derobert ل). لالقيم المنطقية، ولكن حتى 386 كان الخيار فروع، تعليمات setcc، التي تنتج 0 أو 1 في موقع نتيجة بايت (السجل بايت أو الذاكرة). يمكنك أن ترى أيضا أنه في الجواب Derobert، وويجمع هذا الحل أيضا إلى نتيجة تنطوي على setcc (setbe: تعيين إذا كان أقل من أو يساوي).

وDerobert وكريس دولان في ~p | q البديل يجب أن يكون الأسرع لمعالجة كميات كبيرة من البيانات لأنه يمكن معالجة الآثار المترتبة على كل بت من p وq على حدة.

لاحظ أنه حتى الحل !p || q يجمع إلى المتفرعة متاحة على إلى x86: أنه يستخدم تعليمات setcc. هذا هو الحل الأمثل إذا p أو q قد تحتوي على قيم غير صفرية التعسفية التي تمثل صحيح. إذا كنت تستخدم نوع _Bool، فإنه سيتم إنشاء عدد قليل جدا من الإرشادات.

وحصلت على الأرقام التالية عند تجميع لإلى x86:

__attribute__((fastcall)) int imp1(int a, int b)
{
 return ((unsigned int)(a) <= (unsigned int)(b));
}

__attribute__((fastcall)) int imp2(int a, int b)
{
 return (!a || b);
}

__attribute__((fastcall)) _Bool imp3(_Bool a, _Bool b)
{
 return (!a || b);
}

__attribute__((fastcall)) int imp4(int a, int b)
{
 return (~a | b);
}

ونتيجة الجمعية:

00000000 <imp1>:
   0:   31 c0                   xor    %eax,%eax
   2:   39 d1                   cmp    %edx,%ecx
   4:   0f 96 c0                setbe  %al
   7:   c3                      ret    

00000010 <imp2>:
  10:   85 d2                   test   %edx,%edx
  12:   0f 95 c0                setne  %al
  15:   85 c9                   test   %ecx,%ecx
  17:   0f 94 c2                sete   %dl
  1a:   09 d0                   or     %edx,%eax
  1c:   0f b6 c0                movzbl %al,%eax
  1f:   c3                      ret    

00000020 <imp3>:
  20:   89 c8                   mov    %ecx,%eax
  22:   83 f0 01                xor    $0x1,%eax
  25:   09 d0                   or     %edx,%eax
  27:   c3                      ret    

00000030 <imp4>:
  30:   89 d0                   mov    %edx,%eax
  32:   f7 d1                   not    %ecx
  34:   09 c8                   or     %ecx,%eax
  36:   c3                      ret    

عند استخدام نوع _Bool، مترجم يستغل بوضوح أن فقد اثنين من القيم الممكنة فقط (0 لكاذبة و1 لصحيح)، مما ينتج عنه نتيجة مشابهة جدا لحل ~a | b (الفرق الوحيد هو أن هذا الأخير يقوم مكمل على كل بت بدلا من مجرد أدنى بت).

وتجميع 64 بت يعطي تقريبا نفس النتائج.

وعلى أي حال، فمن الواضح، وطريقة لا يهم حقا من وجهة تجنب الشرطية المنتجة.