मैं सी में बिटवाई या अन्य कुशल कोड के साथ तार्किक निहितार्थ कैसे कार्यान्वित कर सकता हूं?

Question

मैं एक लॉजिकल ऑपरेशन को कार्यान्वित करना चाहता हूं जो जितना संभव हो उतना कुशल काम करता है। मैं इस सच्चाई मेज की जरूरत है:

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

यह विकिपीडिया के अनुसार कहा जाता है "logical implication"

मैं लंबे समय से यह पता लगाने की कैसे सशर्त, का उपयोग किए बिना सी में बिटवाइज़ संचालन के साथ इस बनाने के लिए करने की कोशिश कर रहा हूँ। शायद किसी के बारे में कुछ विचार हो गए हैं।

धन्यवाद

Answer 1

FYI करें, जीसीसी-4.3.3 के साथ:

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

(objdump -d से) देता है:

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 

तो, कोई शाखाओं, लेकिन दो बार के रूप में कई निर्देश।

@litb:, का उपयोग कर int के बजाय _Bool एक अच्छा विचार है

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 के साथ है।

Answer 2

!p || q 

बहुत तेजी से होता है। गंभीरता से, इसके बारे में चिंता मत करो।

Answer 3

~p | q 

दृश्य के लिए:

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

तंग कोड में, इस की तुलना में "! पी || q" तेजी होना चाहिए क्योंकि बाद एक शाखा है, जो की वजह से सीपीयू में एक स्टाल के कारण हो सकता है एक शाखा भविष्यवाणी त्रुटि। Bitwise संस्करण निर्धारक है और, बोनस के रूप में, बूलियन संस्करण की तुलना में 32-बिट पूर्णांक में 32 गुना अधिक काम कर सकता है!

Answer 4

आप deriving boolean expressions from truth Tables पर भी पढ़ सकते हैं (canonical form भी देखें), आप कैसे बूलियन प्राइमेटिव या कार्यों के संयोजन के रूप में किसी भी सत्य तालिका को व्यक्त कर सकते हैं।

Answer 5

सी बूलियन्स के लिए एक अन्य समाधान (थोड़ा गंदा है, लेकिन काम करता है):

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

यह सी मानक द्वारा के बाद से काम करता है, 0 झूठी प्रतिनिधित्व करता है, और किसी भी अन्य मान सत्य (1 सच के लिए दिया जाता है बूलियन ऑपरेटर द्वारा, int प्रकार)।

"गंदगी" यह है कि मैं बुलियन (p और q) पूर्णांक के रूप में उपयोग करता हूं, जो कुछ मजबूत टाइपिंग नीतियों (जैसे कि एमआईएसआरए) के विपरीत है, यह एक अनुकूलन प्रश्न है। गंदे सामान को छिपाने के लिए आप मैक्रो के रूप में हमेशा #define कर सकते हैं।

उचित बूलियन p और q (या तो 0 या 1 बाइनरी अभ्यावेदन वाले) यह काम करता है के लिए

। अन्यथा T->TT का उत्पादन करने में विफल हो सकता है यदि p और q में सत्य का प्रतिनिधित्व करने के लिए मनमाने ढंग से nonzero मान हैं।

यदि आपको पेंटियम II के बाद ही परिणाम को स्टोर करने की आवश्यकता है, तो cmovcc (सशर्त मूव) निर्देश (जैसा कि डेरबर्ट के उत्तर में दिखाया गया है) है। बूलियन के लिए, हालांकि 386 में भी एक शाखा रहित विकल्प था, setcc निर्देश, जो 0 या 1 परिणामस्वरूप बाइट स्थान (बाइट रजिस्टर या मेमोरी) में उत्पन्न करता है। आप यह भी देख सकते हैं कि डेरबर्ट के उत्तर में, और यह समाधान setcc (setbe) के परिणामस्वरूप संकलित करता है: नीचे या बराबर सेट करें)।

Derobert और क्रिस डोलन के ~p | q संस्करण डेटा की बड़ी मात्रा के प्रसंस्करण के बाद से यह p और q व्यक्तिगत रूप से सभी बिट्स पर निहितार्थ संसाधित कर सकते हैं के लिए सबसे तेजी से होना चाहिए।

ध्यान दें कि !p || q समाधान x86 पर कोड को ब्रांच करने के लिए संकलित नहीं करता है: यह setcc निर्देशों का उपयोग करता है। यह सबसे अच्छा समाधान है यदि p या q में मनमाना nonzero मान सही प्रतिनिधित्व कर सकते हैं। यदि आप _Bool प्रकार का उपयोग करते हैं, तो यह बहुत कम निर्देश उत्पन्न करेगा।

__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 प्रकार का उपयोग, संकलक स्पष्ट रूप से शोषण करने वाली यह केवल दो संभावित मान है (

मैं निम्नलिखित आंकड़े जब x86 के लिए संकलन मिला 0 गलत के लिए और 1 सत्य के लिए), ~a | b समाधान के लिए एक बहुत ही समान परिणाम का उत्पादन (केवल अंतर यह है कि उत्तरार्द्ध केवल सभी बिट्स पर पूरक बनाता है सबसे कम बिट)।

64 बिट्स के लिए संकलन केवल एक ही परिणाम देता है।

वैसे भी, यह स्पष्ट है कि विधि वास्तव में उत्पादक सशर्तों से बचने के बिंदु से कोई फर्क नहीं पड़ता।