क्या यह है कि C में+ऑपरेटर कैसे लागू किया जाता है?




operators bitwise-operators (6)

मेरा सवाल है: क्या MOST कार्यान्वयन पर पोस्ट किए गए कोड के रूप में + ऑपरेटर को लागू किया गया है?

आइए वास्तविक प्रश्न का उत्तर दें। सभी ऑपरेटरों को कंपाइलर द्वारा कुछ आंतरिक डेटा संरचना के रूप में लागू किया जाता है जो अंततः कुछ परिवर्तनों के बाद कोड में अनुवादित हो जाता है। आप यह नहीं कह सकते कि किस कोड के द्वारा एक एकल जोड़ दिया जाएगा क्योंकि लगभग कोई वास्तविक विश्व संकलक व्यक्तिगत बयानों के लिए कोड नहीं बनाता है।

कंपाइलर किसी भी कोड को उत्पन्न करने के लिए स्वतंत्र है जब तक वह व्यवहार करता है जैसे कि मानक के अनुसार वास्तविक संचालन किया गया था। लेकिन जो वास्तव में होता है वह कुछ पूरी तरह से अलग हो सकता है।

एक सरल उदाहरण:

static int
foo(int a, int b)
{
    return a + b;
}
[...]
    int a = foo(1, 17);
    int b = foo(x, x);
    some_other_function(a, b);

यहां कोई अतिरिक्त निर्देश उत्पन्न करने की आवश्यकता नहीं है। यह संकलक के लिए यह पूरी तरह से कानूनी है:

some_other_function(18, x * 2);

या हो सकता है कि संकलक ने नोटिस किया कि आप फ़ंक्शन को पंक्ति में कई बार foo कहते हैं और यह एक साधारण अंकगणित है और यह इसके लिए वेक्टर निर्देश उत्पन्न करेगा। या इसके अलावा जोड़ के परिणाम का उपयोग बाद में सरणी अनुक्रमण के लिए किया जाता है और अंतिम अनुदेश का उपयोग किया जाएगा।

आप बस इस बारे में बात नहीं कर सकते हैं कि एक ऑपरेटर को कैसे लागू किया जाता है क्योंकि यह लगभग कभी अकेले उपयोग नहीं किया जाता है।

यह समझने के लिए कि कैसे आदिम ऑपरेटरों जैसे कि + , - , * और / को C में लागू किया जाता है, मुझे एक दिलचस्प उत्तर से निम्नलिखित स्निपेट मिला।

// replaces the + operator
int add(int x, int y) {
    while(x) {
        int t = (x & y) <<1;
        y ^= x;
        x = t;
    }
    return y;
}

ऐसा लगता है कि यह फ़ंक्शन दर्शाता है कि पृष्ठभूमि में वास्तव में + कैसे काम करता है। हालाँकि, इसे समझना मेरे लिए बहुत उलझन की बात है। मेरा मानना ​​था कि लंबे समय तक संकलक द्वारा उत्पन्न विधानसभा निर्देशों का उपयोग करके ऐसे ऑपरेशन किए जाते हैं!

क्या MOST कार्यान्वयन पर पोस्ट किए गए कोड के रूप में + ऑपरेटर लागू किया गया है? क्या यह दो पूरक या अन्य कार्यान्वयन-निर्भर सुविधाओं का लाभ उठाता है?


लगता है कि यह फ़ंक्शन दर्शाता है कि पृष्ठभूमि में वास्तव में + कैसे काम करता है

नहीं, इसका अनुवाद देशी add मशीन इंस्ट्रक्शन में किया गया है, जो कि वास्तव में ALU में हार्डवेयर योजक का उपयोग कर रहा है।

यदि आप सोच रहे हैं कि कंप्यूटर कैसे जोड़ता है, तो यहां एक बुनियादी योजक है।

कंप्यूटर में सब कुछ लॉजिक गेट्स का उपयोग करके किया जाता है, जो ज्यादातर ट्रांजिस्टर से बने होते हैं। पूर्ण योजक में अर्ध-योजक होते हैं।

लॉजिक गेट्स और ऐडर्स पर बेसिक ट्यूटोरियल के लिए this देखें। वीडियो बहुत उपयोगी है, हालांकि लंबा है।

उस वीडियो में, एक मूल आधा-योजक दिखाया गया है। यदि आप एक संक्षिप्त विवरण चाहते हैं, तो यह है:

आधा योजक जोड़ने के दो बिट दिए गए हैं। संभावित संयोजन हैं:

  • 0 और 0 = 0 जोड़ें
  • 1 और 0 = 1 जोड़ें
  • 1 और 1 = 10 (बाइनरी) जोड़ें

तो अब आधा योजक कैसे काम करता है? खैर, यह तीन तर्क द्वारों, and , xor और nandnand एक सकारात्मक धारा देता है यदि दोनों इनपुट नकारात्मक हैं, तो इसका मतलब है कि यह 0 और 0. के मामले को हल करता है। xor एक सकारात्मक आउटपुट देता है एक इनपुट सकारात्मक है, और दूसरा नकारात्मक, इसका मतलब है कि यह हल करता है 1 और 0. की समस्या and एक सकारात्मक आउटपुट देता है यदि दोनों इनपुट सकारात्मक हैं, तो यह 1 और 1. की समस्या को हल करता है, इसलिए मूल रूप से, हमें अब अपना आधा-योजक मिल गया है। लेकिन हम अभी भी केवल बिट्स जोड़ सकते हैं।

अब हम अपना पूर्ण-योजक बनाते हैं। एक पूर्ण योजक में बार-बार आधे योजक को कॉल करना शामिल है। अब यह एक कैरी है। जब हम 1 और 1 जोड़ते हैं, तो हमें एक कैरी मिलती है। 1. पूर्ण-योजक क्या करता है, यह आधे-योजक से कैरी लेता है, इसे संग्रहीत करता है, और इसे अर्ध-योजक के एक अन्य तर्क के रूप में पास करता है।

यदि आप भ्रमित हैं कि आप कैरी को कैसे पास कर सकते हैं, तो आप मूल रूप से पहले आधे-योजक का उपयोग करके बिट्स जोड़ते हैं, और फिर योग और कैरी को जोड़ते हैं। तो अब आपने दो बिट्स के साथ कैरी जोड़ा है। इसलिए आप बार-बार ऐसा करते हैं, जब तक कि बिट्स को आपको जोड़ना नहीं पड़ता, तब तक आप अपना परिणाम प्राप्त कर सकते हैं।

आश्चर्य चकित? ऐसा वास्तव में होता है। यह एक लंबी प्रक्रिया की तरह दिखता है, लेकिन कंप्यूटर इसे एक नैनो-सेकेंड के अंशों में, या आधे घंटे के चक्र में अधिक विशिष्ट होने के लिए करता है। कभी-कभी यह एकल घड़ी चक्र में भी किया जाता है। मूल रूप से, कंप्यूटर में ALU ( CPU का एक प्रमुख भाग), मेमोरी, बसें आदि हैं।

यदि आप लॉजिक गेट, मेमोरी और ALU से कंप्यूटर हार्डवेयर सीखना चाहते हैं, और कंप्यूटर का अनुकरण करते हैं, तो आप इस कोर्स को देख सकते हैं, जहाँ से मैंने यह सब सीखा है: फर्स्ट प्रिंसिपल्स से एक आधुनिक कंप्यूटर बनाएँ

यदि आप ई-प्रमाणपत्र नहीं चाहते हैं तो यह मुफ़्त है। पाठ्यक्रम के भाग दो इस साल वसंत में आ रहे हैं


आपके द्वारा पाया गया कोड यह समझाने की कोशिश करता है कि एक बहुत ही आदिम कंप्यूटर हार्डवेयर "ऐड" इंस्ट्रक्शन को कैसे लागू कर सकता है । मैं कहता हूं "हो सकता है" क्योंकि मैं यह गारंटी दे सकता हूं कि यह विधि किसी भी सीपीयू द्वारा उपयोग नहीं की जाती है, और मैं समझाऊंगा कि क्यों।

सामान्य जीवन में, आप दशमलव संख्याओं का उपयोग करते हैं और आपने उन्हें जोड़ना सीख लिया है: दो संख्याएँ जोड़ने के लिए, आप सबसे कम दो अंकों को जोड़ते हैं। यदि परिणाम 10 से कम है, तो आप परिणाम लिखते हैं और अगले अंक की स्थिति में आगे बढ़ते हैं। यदि परिणाम 10 या अधिक है, तो आप परिणाम माइनस 10 लिखते हैं, अगले अंक पर आगे बढ़ें, आपको 1 और जोड़ने के लिए याद रखें। उदाहरण के लिए: 23 + 37, आप 3 + 7 = 10 जोड़ते हैं, आप 0 लिखते हैं और अगली स्थिति के लिए 1 और जोड़ना याद करते हैं। 10 वीं स्थिति में, आप (2 + 3) + 1 = 6 जोड़ते हैं और इसे लिखते हैं। परिणाम 60 है।

आप बाइनरी नंबर के साथ सटीक एक ही काम कर सकते हैं। अंतर यह है कि केवल अंक 0 और 1 हैं, इसलिए एकमात्र संभव योग 0, 1, 2 हैं। 32 बिट संख्या के लिए, आप एक के बाद एक अंकों की स्थिति को संभाल लेंगे। और यह है कि वास्तव में आदिम कंप्यूटर हार्डवेयर यह कैसे करेगा।

यह कोड अलग तरह से काम करता है। आप जानते हैं कि दो द्विआधारी अंकों का योग 2 है यदि दोनों अंक 1. हैं, तो यदि दोनों अंक 1 हैं, तो आप अगले बाइनरी स्थिति में 1 और जोड़ेंगे और नीचे लिखेंगे। 0. यही टी की गणना करता है: यह सभी स्थानों को ढूंढता है जहां दोनों बाइनरी अंक 1 हैं (यह &) है और उन्हें अगले अंक की स्थिति (<< 1) पर ले जाता है। फिर यह जोड़ करता है: 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 2 है, लेकिन हम नीचे लिखते हैं 0. यह है कि बहिष्कृत या ऑपरेटर क्या करता है।

लेकिन सभी 1 है कि आप अगले अंक की स्थिति में संभाल करने के लिए संभाल नहीं किया गया है। उन्हें अभी भी जोड़े जाने की आवश्यकता है। इसलिए कोड एक लूप करता है: अगले पुनरावृत्ति में, सभी अतिरिक्त 1 जोड़े जाते हैं।

कोई प्रोसेसर ऐसा क्यों नहीं करता है? क्योंकि यह एक लूप है, और प्रोसेसर को लूप पसंद नहीं है, और यह धीमा है। यह धीमा है, क्योंकि सबसे खराब स्थिति में, 32 पुनरावृत्तियों की आवश्यकता होती है: यदि आप 1 को संख्या 0xffffff (32 1-बिट्स) में जोड़ते हैं, तो पहला पुनरावृत्ति y का बिट 0 सेट करता है और x को 2 पर सेट करता है। दूसरा पुनरावृत्ति बिट्स 1 y और सेट x से 4. और इसी तरह। परिणाम प्राप्त करने के लिए 32 पुनरावृत्तियों लगते हैं। हालाँकि, प्रत्येक पुनरावृत्ति को x और y के सभी बिट्स को संसाधित करना पड़ता है, जो बहुत सारे हार्डवेयर लेता है।

एक आदिम प्रोसेसर चीजों को ठीक उसी तरह से त्वरित तरीके से करता है जिस तरह से आप दशमलव अंकगणित करते हैं, सबसे कम स्थिति से उच्चतम तक। यह 32 कदम भी उठाता है, लेकिन प्रत्येक चरण पिछले बिट स्थिति से केवल दो बिट्स और एक मूल्य को संसाधित करता है, इसलिए इसे लागू करना बहुत आसान है। और यहां तक ​​कि एक आदिम कंप्यूटर में, कोई भी इसे लागू करने के लिए बिना छोरों को लागू कर सकता है।

एक आधुनिक, तेज और जटिल सीपीयू "सशर्त योग योजक" का उपयोग करेगा। विशेष रूप से यदि बिट्स की संख्या अधिक है, उदाहरण के लिए 64 बिट योजक, यह बहुत समय बचाता है।

एक 64 बिट योजक में दो भाग होते हैं: पहला, सबसे कम 32 बिट के लिए एक 32 बिट योजक। वह 32 बिट योजक एक राशि और एक "कैरी" (एक संकेतक जो 1 को अगले बिट स्थिति में जोड़ा जाना चाहिए) पैदा करता है। दूसरा, उच्च 32 बिट्स के लिए दो 32 बिट योजक: एक एक्स + वाई जोड़ता है, दूसरा एक्स + वाई + 1 जोड़ता है। सभी तीन योजक समानांतर में काम करते हैं। फिर जब पहले योजक ने अपने कैरी का उत्पादन किया है, तो सीपीयू सिर्फ चुनता है जो दो परिणामों में से एक x + y या x + y + 1 सही है, और आपके पास पूरा परिणाम है। तो 64 बिट योजक केवल 32 बिट योजक की तुलना में छोटा सा लंबा समय लेता है, न कि दो बार।

32 बिट योजक भागों को फिर से सशर्त योग योजक के रूप में लागू किया जाता है, कई 16 बिट योजक का उपयोग करते हुए, और 16 बिट योजक सशर्त योग योजक होते हैं, और इसी तरह।


जब आप दो बिट्स जोड़ते हैं, तो परिणाम निम्न है: (सत्य तालिका)

a | b | sum (a^b) | carry bit (a&b) (goes to next)
--+---+-----------+--------------------------------
0 | 0 |    0      | 0
0 | 1 |    1      | 0
1 | 0 |    1      | 0
1 | 1 |    0      | 1

इसलिए अगर आप बिटकॉइन एक्सर करते हैं, तो आपको बिना कैरी के ही रकम मिल सकती है। और अगर आप बिटवाइज़ करते हैं और आप कैरी बिट्स प्राप्त कर सकते हैं।

मल्टीबिट संख्या a और b लिए इस अवलोकन का विस्तार करना

a+b = sum_without_carry(a, b) + carry_bits(a, b) shifted by 1 bit left
    = a^b + ((a&b) << 1)

एक बार b 0 :

a+0 = a

तो एल्गोरिथ्म नीचे उबलता है:

Add(a, b)
  if b == 0
    return a;
  else
    carry_bits = a & b;
    sum_bits = a ^ b;
    return Add(sum_bits, carry_bits << 1);

यदि आप पुनरावृत्ति से छुटकारा पा लेते हैं और इसे एक लूप में बदल देते हैं

Add(a, b)
  while(b != 0) {
    carry_bits = a & b;
    sum_bits = a ^ b;

    a = sum_bits;
    b = carrry_bits << 1;  // In next loop, add carry bits to a
  }
  return a;

कोड से ऊपर मन में स्पष्टीकरण के साथ एल्गोरिथ्म सरल होना चाहिए:

int t = (x & y) << 1;

बिट्स ले। दोनों संचालनों में 1 बिट दाईं ओर 1 है तो कैरी बिट 1 है।

y ^= x;  // x is used now

कैरी के बिना जोड़ (कैरी बिट्स की अनदेखी)

x = t;

इसे ले जाने के लिए x का पुन: उपयोग करें

while(x)

अधिक कैरी बिट होने पर दोहराएं

एक पुनरावर्ती कार्यान्वयन (समझने में आसान) होगा:

int add(int x, int y) {
    return (y == 0) ? x : add(x ^ y, (x&y) << 1);
}

लगता है कि यह फ़ंक्शन दर्शाता है कि पृष्ठभूमि में वास्तव में + कैसे काम करता है

आमतौर पर (लगभग हमेशा) पूर्णांक जोड़ मशीन अनुदेश जोड़ने के लिए अनुवाद करता है। यह सिर्फ एक वैकल्पिक कार्यान्वयन का उपयोग करता है बिटवाइज़ एक्सोर और।


बस ब्याज से बाहर, Atmega328P प्रोसेसर पर, avr-g ++ संकलक के साथ, निम्नलिखित कोड -1 घटाकर एक को जोड़ देता है:

volatile char x;
int main ()
  {
  x = x + 1;  
  }

उत्पन्न कोड:

00000090 <main>:
volatile char x;
int main ()
  {
  x = x + 1;  
  90:   80 91 00 01     lds r24, 0x0100
  94:   8f 5f           subi    r24, 0xFF   ; 255
  96:   80 93 00 01     sts 0x0100, r24
  }
  9a:   80 e0           ldi r24, 0x00   ; 0
  9c:   90 e0           ldi r25, 0x00   ; 0
  9e:   08 95           ret

विशेष रूप से ध्यान दें कि ऐड उप-अनुदेश द्वारा किया जाता है (रजिस्टर से निरंतर घटाना) जहां 0xFF इस मामले में प्रभावी रूप से -1 है।

इसके अलावा रुचि यह है कि इस विशेष प्रोसेसर में एक addi निर्देश नहीं है, जिसका अर्थ है कि डिजाइनरों ने सोचा था कि पूरक का एक घटाना करना संकलक-लेखकों द्वारा पर्याप्त रूप से नियंत्रित किया जाएगा।

क्या यह दो पूरक या अन्य कार्यान्वयन-निर्भर सुविधाओं का लाभ उठाता है?

यह कहना शायद उचित होगा कि संकलक-लेखक उस विशेष रूप से वास्तुकला के लिए संभवतया सबसे कुशल तरीके से वांछित प्रभाव (एक संख्या को दूसरे में जोड़कर) को लागू करने का प्रयास करेंगे। यदि उस पूरक को घटाना आवश्यक है, तो यह हो।


यदि कोड का टूटना किसी और की मदद करता है, तो उदाहरण x=2, y=6 :

x शून्य नहीं है, इसलिए y को जोड़ना शुरू करें:

while(2) {

x & y = 2 क्योंकि

        x: 0 0 1 0  //2
        y: 0 1 1 0  //6
      x&y: 0 0 1 0  //2

2 <<1 = 4 क्योंकि << 1 बाईं ओर सभी बिट्स बदलता है:

      x&y: 0 0 1 0  //2
(x&y) <<1: 0 1 0 0  //4

सारांश में, परिणाम है कि, 4 साथ t में t

int t = (x & y) <<1;

अब बिटवाइज़ XOR y^=x लागू करें:

        x: 0 0 1 0  //2
        y: 0 1 1 0  //6
     y^=x: 0 1 0 0  //4

तो x=2, y=4 । अंत में, x=t t+y को रीसेट करके और लूप की शुरुआत में वापस जा कर योग t+y :

x = t;

जब t=0 (या, लूप की शुरुआत में, x=0 ), के साथ समाप्त करें

return y;





bitwise-operators