Integer multiplication division और shift contracts
Arithmetic से पहले widths तय करें
गणितीय product और stored low-bit result अलग हैं। यहाँ n-bit unsigned inputs की सीमा 0 से 2^n−1 है। Full product के लिए 2n bits पर्याप्त हैं, क्योंकि (2^n−1)^2<2^(2n)। यदि स्पष्ट रूप से कहा जाए तो n-bit destination product modulo 2^n रखता है; वह तभी exact है जब full unsigned product के ऊपरी n bits zero हों। ये hardware bit contracts हैं, किसी programming language के overflow नियमों की गारंटी नहीं।
पूर्वज्ञान: binary representation, addition/subtraction, two's complement और registers। हम सरल arithmetic algorithms और उनके invariants निकालते हैं। Shared-register optimizations, Booth recoding, fast multipliers और control-unit design अलग विषय हैं।
Shift-and-add unsigned multiplication
X और Y, n-bit unsigned inputs लें। P और M, 2n-bit unsigned registers हैं; Q, n-bit unsigned register है। शुरू में P=0,M=zero-extended X,Q=Y रखें। ठीक n iterations, i=0…n−1 चलाएँ:
- Q का पुराना low bit पढ़ें। 1 हो तो P को P+M करें, नहीं तो P hold करें।
- इस addition के बाद Q को एक logical right shift करें और zero भरें।
- अगली iteration बची हो तो M को उसके 2n-bit register में एक left shift करें। इस version में P shift नहीं होता।
Test, Q के shift से पहले का bit इस्तेमाल करता है। सभी additions 2n bits में समाते हैं। Iteration i के शुरू में M=X·2^i,Q=floor(Y/2^i),P=X·(Y mod 2^i) हैं। इसलिए conditional addition ठीक multiplier bit i का contribution जोड़ता है। n iterations बाद सभी multiplier bits process हो चुके होते हैं और P=XY है। किसी दूसरे algorithm का register diagram याद करने से बेहतर यह invariant जाँचना है।
हल किया उदाहरण 1: n=4,X=13=1101,Y=11=1011। P और M आठ bits हैं। नीचे values आसानी के लिए decimal में हैं; Q का low bit अब भी binary decision है।
| i | Step से पहले M | Step से पहले Q | पुराना Q low bit | Optional addition के बाद P |
|---|---|---|---|---|
| 0 | 13 | 11 | 1 | 13 |
| 1 | 26 | 5 | 1 | 39 |
| 2 | 52 | 2 | 0 | 39 |
| 3 | 104 | 1 | 1 | 143 |
Full product 10001111, अर्थात 143 है। केवल चार bits रखने पर 1111=15 मिलता है, exact 143 नहीं। Algorithm में चार bit-inspection iterations और तीन additions हैं। “n iterations” का अर्थ अनिवार्यतः n processor cycles नहीं; hardware schedule को बताना होगा कि कौन-से actions एक cycle में होते हैं।
Invariant से binary long division
Unsigned dividend N और nonzero divisor D के लिए unique Q,R खोजें जिनमें N=QD+R और 0≤R<D हो। दोनों inputs तथा final quotient n bits में हैं। Partial remainder R को n+1-bit unsigned register में शुरू में zero रखें; n-bit quotient Q भी zero हो। Dividend bits b को most significant से least significant क्रम में, ठीक n बार process करें।
पहले n+1 unsigned bits में T=2R+b बनाएँ। यदि T≥D, तो नया R=T−D और अगला quotient bit q=1; अन्यथा नया R=T,q=0। फिर Q=2Q+q करें, जहाँ दाईं ओर पुराना partial quotient है। D न बदलें। हर iteration का T पिछली iteration का remainder इस्तेमाल करता है, पहले से update हुआ remainder नहीं।
एक subtraction पर्याप्त क्यों? पुराना invariant R<D बताता है कि T≤2D−1। इसलिए जरूरत पर D एक बार घटाने से नया remainder फिर 0…D−1 में आ जाता है। Processed dividend prefix Q_old D+R_old था, तो b जोड़कर नया prefix (2Q_old)D+(2R_old+b) है। चुना quotient bit और remainder इस equality को बचाते हैं। अंतिम bit के बाद prefix पूरा N है।
यह compare-before-subtract version restoring decision के equivalent है: trial T−D निकालें, nonnegative हो तो रखें, अन्यथा T restore करके quotient bit zero जोड़ें। Trial को सच में implement करते समय T और D पहले n+2-bit signed temporaries में zero-extend करें, ताकि positive operands और negative trial अस्पष्ट न हों। Unsigned T के top bit को sign न पढ़ें। अधिक compact divider designs के register invariants अलग हो सकते हैं।
हल किया उदाहरण 2: n=4 में 1101₂=13 को 0011₂=3 से भाग दें।
| आने वाला dividend bit | T=2R+b | निर्णय | नया R | Quotient prefix |
|---|---|---|---|---|
| 1 | 1 | T<3 | 1 | 0 |
| 1 | 3 | 3 घटाएँ | 0 | 01 |
| 0 | 0 | T<3 | 0 | 010 |
| 1 | 1 | T<3 | 1 | 0100 |
अंत में Q=4,R=1। जाँच: 13=4·3+1 और 0≤1<3। Remainder bound जरूरी है: Q=3,R=4 equation तो पूरा करते हैं, लेकिन valid division result नहीं हैं। D=0 को शुरू होने से पहले reject करें; इस पाठ में division by zero का मनमाना quotient तय नहीं है।
Signed multiplication और division
Signed two's-complement multiplication का सरल तरीका है nonnegative magnitudes निकालना, उन्हें unsigned multiply करना और product sign लगाना। किसी n-bit signed input की magnitude 2^(n−1) हो सकती है, जो n unsigned bits में समाती है, n signed bits में नहीं। दूसरा तरीका signed input को widen करके absolute value लेना है। Most-negative operand को उसी signed width में negate करके positive signed result मिलने की धारणा न बनाएँ।
दो n-bit signed inputs का exact product, 2n-bit two's complement में समाता है। उदाहरण: चार-bit −7 को +3 से गुणा करने पर −21, आठ-bit 11101011 है। चार low bits रखने पर 1011=−5 आता है, इसलिए चार-bit result overflow करता है। Signed narrowing में मान बचाने के लिए हटने वाले सभी bits retained sign bit की copies होने चाहिए; केवल high bits zero जाँचना unsigned test है।
Signed division में हमारा contract quotient को zero की ओर truncate करता है। Magnitudes divide करें, quotient sign operands के signs का XOR रखें और nonzero remainder का sign dividend जैसा रखें। तब N=QD+R और |R|<|D| हैं। उदाहरण: −13 को +3 से भाग देने पर Q=−4,R=−1, क्योंकि −13=(−4)·3−1। Floor division में Q=−5,R=2 होता; वह अलग valid convention है, हमारा नहीं। Division by zero और most-negative को −1 से divide करने के लिए स्पष्ट exception/overflow handling चाहिए; दूसरे case का quotient उसी signed width में नहीं समाता।
Shifts हर प्रकार का division नहीं हैं
n-bit unsigned U और 0≤k<n के लिए logical right shift k, floor(U/2^k) देता है। Low-n-bit retention वाला left shift, U·2^k modulo 2^n देता है; गणितीय मान fit हो तभी exact है। Two's-complement S का arithmetic right shift sign bit दोहराता है और floor(S/2^k) देता है, हमेशा zero की ओर truncation नहीं।
हल किया उदाहरण 3: चार-bit −7, 1001 है। एक arithmetic right shift से 1100=−4 मिलता है, जबकि zero की ओर truncate किया division by two, −3 देता है। S nonnegative हो या negative S, 2^k से ठीक divisible हो, तो दोनों rounding choices समान हैं। उसी pattern का logical right shift 0100=+4 देता है, जो तीसरा परिणाम है।
मुख्य बातें और सामान्य गलतियाँ
Full product, retained bits और representability test अलग रखें। Multiplication में पुराना multiplier bit जाँचें और दूसरे algorithm का update order न मिलाएँ। Division में reconstruction equation और remainder bound दोनों जाँचें। Signed rounding और zero-divisor behavior लिखें। Sign-preserving shift एक bit operation है जिसका विशेष rounding परिणाम है; वह हर language के division का स्वतः विकल्प नहीं।
मौलिक अभ्यास
ये छह single-correct MCQ सीखने के लिए बनाए गए मौलिक प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। हर प्रश्न में ठीक एक विकल्प चुनें।
C01. Unsigned चार-bit inputs 13 और 11 का full आठ-bit product तथा retained low चार bits क्या हैं?
A. 10001111 और 1111 B. 00001111 और 1111 C. 10001111 और 1000 D. 01110001 और 0001
उत्तर: A
A सही है: 13×11=143=128+15, इसलिए full 10001111 और low 1111।
B गलत है: 15 केवल retained low-bit मान है, full product नहीं।
C गलत है: 1000 high nibble है, low नहीं।
D गलत है: 01110001, 113 है, 143 नहीं।
C02. बताए shift/add algorithm में X=9,Y=6,n=4। दो iterations के बाद P क्या है?
A. 9 B. 54 C. 18 D. 27
उत्तर: C
A गलत है: multiplier bit 0 zero है, इसलिए X पहले नहीं जुड़ता।
B गलत है: 54, bit 2 भी process होने के बाद full product है।
C सही है: 0110 के bits 0,1 क्रमशः 0,1 हैं, इसलिए P=0+18=18।
D गलत है: bit-0 contribution 9 गलत जोड़ा।
C03. N=29,D=5 के लिए कौन-सा unsigned quotient/remainder pair valid है?
A. Q=4,R=9 B. Q=5,R=4 C. Q=6,R=−1 D. Q=5,R=5
उत्तर: B
A गलत है: 29 reconstruct होता है, लेकिन R<D नहीं।
B सही है: 29=5×5+4 और 0≤4<5।
C गलत है: unsigned division में remainder nonnegative चाहिए।
D गलत है: इससे 30 बनता है और R<D भी गलत है।
C04. Signed quotient को zero की ओर truncate करते हुए −19 को +4 से भाग दें।
A. Q=−5,R=1 B. Q=−4,R=3 C. Q=4,R=−3 D. Q=−4,R=−3
उत्तर: D
A गलत है: यह floor division है, बताया truncation नहीं।
B गलत है: −4×4+3=−13 है, −19 नहीं।
C गलत है: quotient sign और equation दोनों गलत हैं।
D सही है: −19=(−4)×4−3, |−3|<4 और quotient zero की ओर truncate है।
C05. चार-bit two's-complement 1001 के लिए arithmetic-right-shift-by-one और zero की ओर truncate किए division by two के परिणाम कौन-से हैं?
A. −4 और −3 B. −3 और −4 C. +4 और −3 D. −4 और −4
उत्तर: A
A सही है: 1001=−7; ASR से 1100=−4, जबकि trunc(−7/2)=−3।
B गलत है: floor और truncation उलटे हैं।
C गलत है: +4 logical shift है, arithmetic नहीं।
D गलत है: negative odd संख्या का zero की ओर division, floor से अलग है।
C06. n≥2 में कौन-सा nonzero-divisor case n-bit two's-complement quotient को अनिवार्यतः overflow करता है?
A. 0 को −1 से divide करना B. Most-negative को +1 से divide करना C. Most-negative को −1 से divide करना D. Greatest-positive को +1 से divide करना
उत्तर: C
A गलत है: zero quotient समाता है।
B गलत है: मूल most-negative मान समाता है।
C सही है: +2^(n−1), अधिकतम positive 2^(n−1)−1 से अधिक है।
D गलत है: मूल greatest-positive मान समाता है।
सीमा और स्रोत
यह Digital Logic के एक सीमित हिस्से का पाठ है, पूरे GATE CS की तैयारी नहीं। आधिकारिक पाठ्यक्रम केवल विषय की प्रासंगिकता की पुष्टि करता है; व्युत्पत्तियाँ, उदाहरण और अभ्यास मौलिक हैं। तकनीकी संदर्भों से representation और circuit की conventions जाँची गई हैं; उनके अभ्यास प्रश्न नहीं दोहराए गए।
स्रोत 14 अक्टूबर 2026 को जाँचे गए।
प्रगति सहेजने के लिए साइन इन करें। साइन इन