Integer multiplication division and shift contracts
Fix widths before doing arithmetic
A mathematical product and a stored low-bit result are different objects. Here n-bit unsigned inputs range from 0 through 2^n−1. A full product uses 2n bits, since (2^n−1)^2<2^(2n). An n-bit destination instead stores the product modulo 2^n if explicitly specified; it is exact only when the high n bits of the full unsigned product are zero. These are hardware bit contracts, not promises about a programming language's overflow rules.
Prerequisites: binary representation, addition/subtraction, two's complement and registers. We derive simple arithmetic algorithms and their invariants. Detailed shared-register optimizations, Booth recoding, fast multipliers and control-unit design are separate topics.
Shift-and-add unsigned multiplication
Let X and Y be n-bit unsigned inputs. Allocate P and M as 2n-bit unsigned registers, and Q as an n-bit unsigned register. Initialize P=0, M=zero-extended X, Q=Y. Perform exactly n iterations numbered i=0…n−1:
- Read the old low bit of Q. If it is 1, set P to P+M; otherwise hold P.
- After that addition, shift Q right logically by one, inserting zero.
- If another iteration remains, shift M left by one within its 2n-bit register. Do not shift P in this version.
The test uses Q before its shift. All additions here fit 2n bits. At the start of iteration i, M=X·2^i, Q=floor(Y/2^i), and P=X·(Y mod 2^i). Therefore the conditional addition includes precisely the contribution of multiplier bit i. After n iterations all multiplier bits have been processed and P=XY. This invariant is a better check than memorizing a register diagram from a different algorithm.
Worked example 1: n=4, X=13=1101 and Y=11=1011. P and M are eight bits. Values below are decimal for readability; Q's low bit is still the binary decision.
| i | M before step | Q before step | Old Q low bit | P after optional addition |
|---|---|---|---|---|
| 0 | 13 | 11 | 1 | 13 |
| 1 | 26 | 5 | 1 | 39 |
| 2 | 52 | 2 | 0 | 39 |
| 3 | 104 | 1 | 1 | 143 |
The full product is 10001111, or 143. Retaining just four bits gives 1111=15, not exact 143. This algorithm performs four bit-inspection iterations and three additions; “n iterations” does not necessarily mean n processor cycles, since a hardware schedule has to specify which actions share a cycle.
Binary long division from an invariant
For unsigned dividend N and nonzero divisor D, find unique Q,R with N=QD+R and 0≤R<D. Let both inputs and final quotient use n bits. Use an n+1-bit unsigned partial remainder register R, initially zero, and an n-bit quotient Q, initially zero. Process dividend bits b from most significant to least significant, exactly n times.
First form T=2R+b in n+1 unsigned bits. If T≥D, set new R=T−D and next quotient bit q=1; otherwise set new R=T and q=0. Then set Q=2Q+q, using the old partial quotient on the right. Keep D unchanged. Each iteration's T uses the previous iteration's remainder, not an already updated remainder.
Why is one subtraction sufficient? The old invariant R<D implies T≤2D−1. Therefore subtracting D once when needed puts the new remainder back in 0…D−1. If a processed dividend prefix was Q_old D+R_old, appending bit b makes it (2Q_old)D+(2R_old+b). The selected quotient bit and remainder preserve that equality. After the last bit, the prefix is the whole N.
This compare-before-subtract version is equivalent to a restoring decision: compute trial T−D, keep it when nonnegative, otherwise restore T and append quotient bit zero. If implementing that trial literally, first zero-extend T and D into n+2-bit signed temporaries so positive operands and a negative trial are unambiguous; do not read an unsigned T's top bit as a sign. Other compact divider designs exist but use different register invariants.
Worked example 2: divide 1101₂=13 by 0011₂=3, n=4.
| Incoming dividend bit | T=2R+b | Decision | New R | Quotient prefix |
|---|---|---|---|---|
| 1 | 1 | T<3 | 1 | 0 |
| 1 | 3 | subtract 3 | 0 | 01 |
| 0 | 0 | T<3 | 0 | 010 |
| 1 | 1 | T<3 | 1 | 0100 |
Final Q=4 and R=1; verify 13=4·3+1 and 0≤1<3. The remainder bound is essential: Q=3,R=4 satisfies the equation but is not a valid division result. D=0 is rejected before starting; this lesson defines no fabricated quotient for division by zero.
Signed multiplication and division
For signed two's-complement multiplication, one simple route is to extract nonnegative magnitudes, multiply them unsigned, and apply the product sign. An n-bit signed input's magnitude may be 2^(n−1), which fits n unsigned bits but not n signed bits. Alternatively widen the signed input before taking its absolute value. Never negate the most-negative operand in the same signed width and assume a positive signed result was obtained.
Two n-bit signed inputs have an exact product representable in 2n-bit two's complement. Example: four-bit −7 times +3 is −21, encoded as eight-bit 11101011. Keeping four low bits yields 1011=−5, so the four-bit result overflows. For signed narrowing, the discarded bits must all be copies of the retained sign bit for value preservation; checking only for zero high bits is an unsigned test.
For signed division, this lesson chooses quotient truncation toward zero. Divide magnitudes, give the quotient the XOR of operand signs, and give a nonzero remainder the dividend's sign. Then N=QD+R and |R|<|D|. Example: −13 divided by +3 gives Q=−4,R=−1, because −13=(−4)·3−1. Floor division instead gives Q=−5,R=2; it is a different valid convention, not ours. Division by zero and most-negative divided by −1 require explicit exception/overflow handling; the latter quotient does not fit the same signed width.
Shifts are not universally division
For an n-bit unsigned U, logical right shift by k with 0≤k<n gives floor(U/2^k). Left shift with low-n-bit retention gives U·2^k modulo 2^n; it is exact only if the mathematical value fits. For two's-complement S, arithmetic right shift repeats the sign bit and gives floor(S/2^k), not always truncation toward zero.
Worked example 3: four-bit −7 is 1001. Arithmetic right shift one yields 1100=−4, whereas truncation-toward-zero division by two gives −3. For nonnegative S, or a negative S exactly divisible by 2^k, those two rounding choices coincide. Logical right shift of the same pattern gives 0100=+4, a third result.
Key points and common mistakes
Keep the full product, retained bits and representability test separate. In multiplication test the old multiplier bit and do not mix update orders from another algorithm. In division verify both the reconstruction equation and the remainder bound. State signed rounding and zero-divisor behavior. A sign-preserving shift is a bit operation with a particular rounding consequence, not an automatic substitute for every language's division.
Original practice
These six single-correct MCQs are original learning questions, not previous-year questions. Choose exactly one option.
C01. For unsigned 4-bit inputs 13 and 11, what are the full 8-bit product and the retained low four bits?
A. 10001111 and 1111 B. 00001111 and 1111 C. 10001111 and 1000 D. 01110001 and 0001
Answer: A
A is correct: 13×11=143=128+15, hence full 10001111 and low 1111.
B is incorrect: 15 is only the retained low-bit value, not the full product.
C is incorrect: 1000 is the high nibble, not the low nibble.
D is incorrect: 01110001 is 113, not 143.
C02. In the stated shift/add algorithm, X=9,Y=6,n=4. After two iterations, what is P?
A. 9 B. 54 C. 18 D. 27
Answer: C
A is incorrect: multiplier bit 0 is zero, so X is not added first.
B is incorrect: 54 is the completed product after processing bit 2 as well.
C is correct: bits 0 and 1 of 0110 are 0 and 1, so P=0+18=18.
D is incorrect: it incorrectly adds the bit-0 contribution 9.
C03. Which unsigned quotient/remainder pair is valid for N=29,D=5?
A. Q=4,R=9 B. Q=5,R=4 C. Q=6,R=−1 D. Q=5,R=5
Answer: B
A is incorrect: it reconstructs 29 but violates R<D.
B is correct: 29=5×5+4 and 0≤4<5.
C is incorrect: unsigned division requires a nonnegative remainder.
D is incorrect: it reconstructs 30 and also violates R<D.
C04. With signed quotient truncation toward zero, divide −19 by +4.
A. Q=−5,R=1 B. Q=−4,R=3 C. Q=4,R=−3 D. Q=−4,R=−3
Answer: D
A is incorrect: this is floor division, not the declared truncation.
B is incorrect: −4×4+3=−13, not −19.
C is incorrect: quotient sign is wrong and the equation fails.
D is correct: −19=(−4)×4−3, |−3|<4, and quotient truncates toward zero.
C05. For 4-bit two's-complement 1001, which pair gives arithmetic-right-shift-by-one and truncation-toward-zero division by two?
A. −4 and −3 B. −3 and −4 C. +4 and −3 D. −4 and −4
Answer: A
A is correct: 1001=−7; ASR gives 1100=−4, whereas trunc(−7/2)=−3.
B is incorrect: it reverses floor and truncation.
C is incorrect: +4 is the logical-shift result, not arithmetic shift.
D is incorrect: negative odd division toward zero differs from flooring.
C06. Which nonzero-divisor case necessarily overflows an n-bit two's-complement quotient, n≥2?
A. 0 divided by −1 B. Most-negative value divided by +1 C. Most-negative value divided by −1 D. Greatest-positive value divided by +1
Answer: C
A is incorrect: quotient zero fits.
B is incorrect: the original most-negative value itself fits.
C is correct: +2^(n−1) exceeds the greatest positive value 2^(n−1)−1.
D is incorrect: the original greatest-positive value fits.
Scope and sources
This is one bounded Digital Logic lesson, not complete GATE CS coverage. The official syllabus establishes relevance only; the derivations, examples and practice are original. Technical references were used to check representation and circuit conventions, not to reproduce their exercises.
Sources checked 14 October 2026.
Sign in to keep your progress. Sign in