Two's complement में signed पूर्णांक और overflow
Representation क्या तय करती है
Bit pattern अपने आप signed या unsigned नहीं होता। चार bits में 1101 का unsigned अर्थ 13 है, लेकिन two's complement में −3 है। इस पाठ में निश्चित width वाले two's-complement पूर्णांक और ऐसा आदर्श adder लेते हैं जो ठीक n निचले bits रखता है। इससे यह नहीं मानते कि कोई programming language signed wraparound की अनुमति देती है। हर सवाल में पहले width, representation और माँगा गया परिणाम लिखें।
पूर्वज्ञान: unsigned place values, binary addition और सामान्य Boolean gates। लक्ष्य: signed मान encode और decode करना, मान बदले बिना width बढ़ाना, और signed overflow को unsigned carry से अलग करना। Sign-magnitude, one's complement, गुणा, भाग तथा floating point अलग पाठों के विषय हैं।
Bits b_(n−1)…b_0 में सबसे ऊपरी bit का भार −2^(n−1) और बाकी bits के भार सामान्य धनात्मक घातें हैं। इसलिए मान = −b_(n−1)×2^(n−1) + Σ b_i×2^i, जहाँ i=0…n−2 है। दूसरा तरीका: पहले pattern को unsigned U पढ़ें। ऊपरी bit 0 हो तो मान U; ऊपरी bit 1 हो तो मान U−2^n। दूसरे नियम में 2^n घटता है, 2^(n−1) नहीं।
मानों की सीमा और decoding
सबसे छोटा मान 1 के बाद सभी zeros से मिलता है: −2^(n−1)। सबसे बड़ा मान 0 के बाद सभी ones से मिलता है: 2^(n−1)−1। कुल patterns अब भी 2^n हैं और zero का केवल एक encoding है। सीमा असममित है क्योंकि एक गैर-ऋणात्मक pattern zero के लिए है।
| चार-bit pattern | Unsigned मान U | Two's-complement मान |
|---|---|---|
| 0000 | 0 | 0 |
| 0111 | 7 | 7 |
| 1000 | 8 | −8 |
| 1101 | 13 | −3 |
| 1111 | 15 | −1 |
हल किया उदाहरण 1: छह-bit pattern 101101 पढ़ें। ऋणात्मक भार से: −32+8+4+1=−19। Unsigned तरीके से: U=45 और 45−64=−19। दोनों स्वतंत्र जाँचें समान उत्तर देती हैं। अंतिम पाँच bits को अलग magnitude मानने से −13 मिलता, जो दूसरी encoding convention है।
Encoding और negation
ऋणात्मक मान −m को n bits में लिखने से पहले जाँचें कि 1≤m≤2^(n−1) है। फिर 2^n−m को उसी width में unsigned लिखें। दूसरा तरीका: m के n-bit unsigned pattern के हर bit को उलटें और 1 जोड़ें; n bits रखें। Complement करने पर 2^n−1−m मिलता है और 1 जोड़ने पर 2^n−m। इससे नियम का कारण समझ आता है।
हल किया उदाहरण 2: −23 को आठ bits में encode करें। 23=00010111 से शुरू करें; bits उलटने पर 11101000 और 1 जोड़ने पर 11101001। जाँच: U=233 और 233−256=−23। छह bits से शुरू करने पर width अलग होगी, लेकिन लगातार छह-bit नियम लगाने पर मान वही रहेगा। −23 छह bits में समाता है क्योंकि −32≤−23≤31 है।
एक सीमा बहुत महत्वपूर्ण है। सबसे छोटे n-bit मान का negative लेने के लिए +2^(n−1) चाहिए, जो उसी width में नहीं समाता। चार bits में 1000 को उलटने पर 0111 और 1 जोड़ने पर फिर 1000 मिलता है। Bit operation पूरा हुआ, लेकिन representable +8 नहीं मिला। Exact धनात्मक उत्तर चाहिए तो पहले width बढ़ाएँ। Zero को negate करने पर अतिरिक्त carry छोड़ने के बाद zero ही मिलता है।
Sign extension से मान सुरक्षित रहता है
Two's-complement मान की width बढ़ाते समय मूल ऊपरी bit को हर नए ऊपरी स्थान पर दोहराएँ। चार-bit 1011 का मान −5 है; आठ-bit 11111011 का भी −5 है। इसके बजाय 00001011 बनाने पर +11 मिलेगा। धनात्मक मानों में दोनों विधियाँ leading zeros देती हैं।
यह क्यों काम करता है? किसी ऋणात्मक pattern में एक नया ऊपरी 1 जोड़ने पर ऋणात्मक भार −2^(n−1) से −2^n हो जाता है, जबकि पुराना sign bit अब +2^(n−1) जोड़ता है। दोनों का योग फिर −2^(n−1) है। हर नए स्थान के लिए यही तर्क लागू होता है। मनमाने high bits हटाना इसका उलटा नहीं है: width घटाने से मान तभी सुरक्षित है जब वह नई सीमा में समाए।
Addition और signed overflow
सामान्य binary addition करें और n bits रखें। Retained pattern को signed नियम से पढ़ें। Exact गणितीय योग तभी representable है जब वह n-bit signed सीमा में आए। Addition में signed overflow ठीक तब होता है जब दोनों operands के signs समान हों और retained result का sign उलट हो। अलग signs जोड़ने पर overflow नहीं होता, क्योंकि परिणाम दोनों operands के बीच रहता है।
हल किया उदाहरण 3: चार bits में 0101+0100 =1001। Exact signed योग 5+4=9 है, जो −8…7 से बाहर है। Retained pattern −7 दर्शाता है, इसलिए signed overflow 1 है। सबसे ऊपरी स्थान के बाहर carry नहीं निकला, इसलिए carry-out 0 है। यह “overflow का अर्थ carry-out है” का सीधा counterexample है।
इसके विपरीत 1110+1101 =1 1011 लें। Signed operands −2 और −3 हैं; retained 1011 का मान −5 है, जो सही है। Carry-out 1 लेकिन signed overflow 0 है। इन्हीं inputs को unsigned मानें तो 14+13=27 होगा और unsigned overflow होगा। एक ही hardware addition के flags अलग interpretations के सवालों का उत्तर देते हैं।
दूसरी जाँच है V = sign bit में आने वाला carry XOR sign bit से बाहर जाने वाला carry। दोनों carries उसी n-bit addition के होने चाहिए, जिसमें दिया गया input carry भी शामिल हो। बिना initial carry वाले सामान्य दो-operand addition में ऊपर वाला sign नियम अक्सर सरल है।
Subtraction और भरोसेमंद विधि
a−b के लिए a में b का bitwise complement और 1 जोड़ें, फिर n bits रखें। Exact अंतर को signed सीमा से जाँचें। Subtraction का sign नियम यह है: a और b के signs अलग हों तथा result का sign a से अलग हो तो overflow है। Addition वाला sign नियम सीधे a और b पर न लगाएँ। यदि b सबसे छोटा मान है, तो यह भी न मानें कि बीच का गणितीय मान −b उसी width में समाता है।
हल किया उदाहरण 4: चार-bit 3−(−6) के लिए 0011 + complement(1010) + 1 =0011+0101+0001 =1001। गणितीय अंतर 9 है, इसलिए −7 वाला pattern overflow बताता है। इसके विपरीत −3−2 में 1101+1101+0001 =1 1011 मिलता है; retained 1011 का मान −5 है और सीमा में है। Subtraction carry को borrow समझने का नियम convention पर निर्भर करता है; यहाँ exact signed सीमा से जाँच करते हैं।
मुख्य बातें और सामान्य गलतियाँ
- पहले decode करें, exact integer निकालें, सीमा जाँचें, फिर retained bits का अर्थ पढ़ें।
- चार-bit signed सीमा −8…7 है, −7…7 या −8…8 नहीं।
- ऊपरी bit का भार ऋणात्मक है; वह अलग निकाल सकने वाला minus sign नहीं है।
- Sign extension में sign bit दोहरता है। ऋणात्मक pattern के आगे zeros जोड़ने से मान बदलता है।
- केवल carry-out signed overflow नहीं बताता। Exact योग और stored pattern अलग रखें।
- सबसे छोटे मान को उसी width में exact negate नहीं कर सकते। Hardware bits का व्यवहार C-language semantics की गारंटी नहीं है।
मौलिक अभ्यास
ये छह single-correct MCQ सीखने के लिए बनाए गए मौलिक प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। हर प्रश्न में ठीक एक विकल्प चुनें।
C01. छह-bit two's-complement pattern 110101 का मान क्या है?
A. 53 B. −21 C. −11 D. −13
उत्तर: C
A गलत है: 53 unsigned व्याख्या है।
B गलत है: नीचे के पाँच bits को magnitude मानने से −21 मिलता है।
C सही है: unsigned U=53 और 53−64=−11; भारों से भी −32+16+4+1=−11।
D गलत है: −13 का छह-bit pattern 110011 है।
C02. −37 का आठ-bit two's-complement pattern कौन-सा है?
A. 11011010 B. 11011011 C. 10100101 D. 00100101
उत्तर: B
A गलत है: 00100101 को उलटकर 1 न जोड़ने पर −38 मिलता है।
B सही है: 256−37=219 और उसका आठ-bit pattern 11011011 है।
C गलत है: 10100101 का अर्थ 165−256=−91 है, −37 नहीं।
D गलत है: 00100101 धनात्मक 37 है।
C03. पाँच-bit two's-complement मान 10110 को मान बदले बिना आठ bits में बढ़ाएँ।
A. 00010110 B. 10010110 C. 11110110 D. 11100110
उत्तर: C
A गलत है: zero-extension से −10 बदलकर +22 हो जाता है।
B गलत है: 10010110 का मान −106 है, −10 नहीं।
C सही है: तीनों नए स्थानों में sign bit 1 दोहराएँ; 246−256=−10।
D गलत है: 11100110 का मान −26 है; मूल bit बदल दिया गया है।
C04. चार-bit adder input carry 0 के साथ 0110+0011 करता है। (Retained pattern, carry-out, signed overflow) क्या हैं?
A. 1001, 1, 1 B. 1001, 0, 0 C. 1001, 0, 1 D. 0111, 0, 1
उत्तर: C
A गलत है: unsigned 6+3=9, 16 से कम है, इसलिए carry-out 0 है।
B गलत है: +9 signed अधिकतम +7 से बड़ा है, इसलिए signed overflow 1 है।
C सही है: low pattern 1001 है, पाँचवें bit का carry नहीं और signed योग सीमा से बाहर है।
D गलत है: 0111 का मान 7 है; saturation का नियम नहीं दिया गया।
C05. चार-bit two's complement में किस addition का carry-out 1 है लेकिन signed overflow नहीं?
A. 0101+0100 B. 1001+1010 C. 0111+0001 D. 1110+1101
उत्तर: D
A गलत है: 5+4=9 में signed overflow है और carry-out 0 है।
B गलत है: −7+(−6)=−13, −8 से कम है; carry-out 1 होने के साथ signed overflow भी है।
C गलत है: 7+1=8 में signed overflow है और carry-out 0 है।
D सही है: −2+(−3)=−5 सीमा में है; raw 14+13=27 से low 1011 और carry-out 1 मिलता है।
C06. चार-bit pattern 1000 के bits उलटकर 1 जोड़ें और चार bits रखें। क्या होगा?
A. Pattern 1000 है, लेकिन −8 का exact negation चार-bit two's complement में नहीं समाता। B. Pattern 0000 है, क्योंकि हर संख्या खुद को निरस्त करती है। C. Pattern 0111 है और +8 दर्शाता है। D. Pattern 1000 है और चार-bit two's complement में +8 दर्शाता है।
उत्तर: A
A सही है: उलटने पर 0111 और 1 जोड़ने पर 1000; गणितीय +8, −8…7 से बाहर है।
B गलत है: negate करना संख्या को खुद से जोड़ना नहीं है।
C गलत है: 0111 बीच का complement है और +7 दर्शाता है।
D गलत है: retained pattern अब भी −8 है, +8 नहीं।
सीमा और स्रोत
यह Digital Logic के एक सीमित हिस्से का पाठ है, पूरे GATE CS की तैयारी नहीं। आधिकारिक पाठ्यक्रम केवल विषय की प्रासंगिकता की पुष्टि करता है; व्युत्पत्तियाँ, उदाहरण और अभ्यास मौलिक हैं। तकनीकी संदर्भों से representation और circuit की conventions जाँची गई हैं; उनके अभ्यास प्रश्न नहीं दोहराए गए।
- Official GATE 2027 CS syllabus Section 2
- MIT Computation Structures binary encoding
- Cornell two's-complement notes
स्रोत 14 अक्टूबर 2026 को जाँचे गए।
प्रगति सहेजने के लिए साइन इन करें। साइन इन