Skip to content
CampusPrep
AD-503 (C) · Computer Org. & Architecture/Quick Revision Short Notes

Computer Org. & Architecture (AD-503 (C)) - Unit 2 Short Notes

How unit 2 is examined

This unit covers binary addition and subtraction, two's complement, overflow, multiplication, Booth's algorithm, division, IEEE 754 floating point and the arithmetic unit. No question from these topics appeared in the supplied papers, so every topic is short but complete.

Addition and Subtraction

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. Binary addition adds bits column by column with a carry; binary subtraction is done in hardware by adding the complement of the subtrahend.

Key points.

  1. The rules are $0+0=0$, $0+1=1$, $1+1=10$ (sum 0, carry 1) and $1+1+1=11$.
  2. A full adder takes bits $A$, $B$ and carry-in $C_{in}$ and gives $S = A \oplus B \oplus C_{in}$ and $C_{out} = AB + C_{in}(A \oplus B)$.
  3. Subtraction $A-B$ is performed as $A + \overline{B} + 1$, so one adder serves both operations.
  4. Example: $0110 + 0011 = 1001$ (6 + 3 = 9).
  5. Example of subtraction: $7 - 3$ in 4 bits is $0111 + 1101 = 1\ 0100$; discarding the carry gives $0100 = 4$.

Answer frame. Open with the full-adder equations; give one addition and one subtraction example; close by noting a single adder does both.

<mark>Binary subtraction is performed by adding the two's complement of the subtrahend, so no separate subtractor is needed.</mark>

Answer frame. Open with the definition; list the rules with one example each; close with the single-zero advantage.

Number (4 bits) Sign-magnitude One's complement Two's complement
+5 0101 0101 0101
-5 1101 1010 1011
Zero +0 and -0 +0 and -0 one zero
Range -7 to +7 -7 to +7 -8 to +7

Two's Complement Representation

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. Two's complement is the signed-number code in which a negative number $-N$ is stored as $2^n - N$ using $n$ bits.

Key points.

  1. To form it, invert every bit (one's complement) and add 1; for example $0101$ (5) becomes $1010+1=1011$ (-5).
  2. The MSB is the sign bit: 0 means positive and 1 means negative.
  3. The range for $n$ bits is $-2^{n-1}$ to $2^{n-1}-1$, so 4 bits give -8 to +7.
  4. Zero has only one representation, unlike sign-magnitude and one's complement.
  5. Addition and subtraction need no sign-checking logic, which is why it is used in every computer.

==Two's complement = invert all bits and add 1; it has a single zero and range $-2^{n-1}$ to $2^{n-1}-1$.==

Answer frame. Open with the two's-complement rule; state the overflow condition; show the 5 + 4 example; close with the XOR formula.

Example. In 4 bits, $5 + (-3)$: $0101 + 1101 = 1\ 0010$. The carry-out is discarded, so the result is $0010 = 2$, with no overflow.

Signed Addition and Subtraction

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. Signed numbers in two's complement are added directly, sign bit included, and the result is valid unless overflow occurs.

Key points.

  1. Subtraction $A-B$ is done as $A + (\text{two's complement of } B)$, and any final carry-out is discarded.
  2. Overflow occurs only when both operands have the same sign and the result has the opposite sign.
  3. Hardware detects it as $V = C_{n-1} \oplus C_n$, the carry into the sign bit XOR the carry out of it.
  4. Example in 4 bits: $0101 + 0100 = 1001$; two positives gave a negative, so overflow (5 + 4 = 9 exceeds 7).
  5. Adding numbers of opposite sign can never overflow.

<mark>Overflow is detected when the carry into the sign bit differs from the carry out of the sign bit.</mark>

Answer frame. Open with the definition; show the shift-and-add table for 5 x 3; then state the register roles; close with the $2n$-bit product.

Example. $5 \times 3$ with multiplicand 101 and multiplier 011:

Multiplier bit Partial product added Running sum
1 (LSB) 101 101
1 1010 1111
0 0000 1111

Product = 001111 = 15.

Multiplication and Division

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. Binary multiplication is repeated shift-and-add of the multiplicand, and binary division is repeated shift-and-subtract of the divisor.

Key points.

  1. Each multiplier bit is examined; if it is 1 the multiplicand is added to the partial product, and if it is 0 nothing is added.
  2. After each step the partial product is shifted one place, so an $n$-bit by $n$-bit multiply gives a $2n$-bit product.
  3. Example: $101 \times 011 = 1111$ (5 x 3 = 15).
  4. Registers used are A (accumulator, initially 0), Q (multiplier), M (multiplicand) and a counter of $n$ steps.
  5. Division works the other way, giving a quotient and a remainder with $\text{Dividend} = \text{Divisor} \times \text{Quotient} + \text{Remainder}$.

<mark>Multiplication is shift-and-add and division is shift-and-subtract, each taking $n$ steps for $n$-bit operands.</mark>

Answer frame. Open with the definition; draw the flowchart as the four steps above; work the example in a table; close by saying it also handles negative multipliers.

Example. $3 \times (-2)$ with M = 011, -M = 101, Q = 110, A = 000, $Q_{-1}=0$:

Step $Q_0Q_{-1}$ Action A Q $Q_{-1}$
1 00 shift 000 011 0
2 10 A - M, shift 110 101 1
3 11 shift 111 010 1

Product = A:Q = 111010 = -6.

Booth's Algorithm

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. Booth's algorithm multiplies two signed two's-complement numbers by examining pairs of multiplier bits $Q_0$ and $Q_{-1}$ and skipping runs of 1s.

Key points.

  1. Registers: A = 0, Q = multiplier, extra bit $Q_{-1}=0$, M = multiplicand, and count = $n$.
  2. If $Q_0 Q_{-1} = 10$, do $A = A - M$; if $01$, do $A = A + M$; if $00$ or $11$, do nothing.
  3. Then arithmetic-shift right A, Q, $Q_{-1}$ together, keeping the sign bit, and decrement the count.
  4. Repeat $n$ times; the product is in A:Q.
  5. Example: $3 \times (-2)$ in 3 bits gives $111010$, which is -6.

<mark>Booth's algorithm treats a run of 1s in the multiplier as $+2^{k+1} - 2^{m}$, so it needs only one subtraction and one addition per run.</mark>

Answer frame. Open with the register roles; write the restoring steps as numbered steps; show the trace; close with the quotient and remainder.

Example. $7 \div 2$ restoring, 3 bits, A = 000, Q = 111, M = 010:

Step Shift A:Q A - M Action A Q
1 001 110 111 (negative) restore, $Q_0=0$ 001 110
2 011 100 001 $Q_0=1$ 001 101
3 011 010 001 $Q_0=1$ 001 011

Quotient = 011 = 3, remainder = 001 = 1.

Division Operation

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. Division of unsigned binary numbers uses registers A (remainder, 0), Q (dividend) and M (divisor) and produces the quotient in Q and remainder in A.

Key points.

  1. Restoring method: shift A:Q left one bit, then compute $A = A - M$.
  2. If A is negative, set $Q_0=0$ and restore A by adding M back; otherwise set $Q_0=1$.
  3. Repeat $n$ times; then Q holds the quotient and A the remainder.
  4. Non-restoring method: if A was negative, shift and add M; otherwise shift and subtract M, restoring only once at the end if needed.
  5. Non-restoring is faster since it avoids the restoring addition in each step.

<mark>Restoring division subtracts the divisor, and if the result is negative it adds the divisor back and sets the quotient bit to 0.</mark>

Answer frame. Open with the IEEE 754 format; draw the field layout as a table; give the steps of addition; close with the worked conversion.

Field Single precision Double precision
Sign 1 bit 1 bit
Exponent 8 bits, bias 127 11 bits, bias 1023
Mantissa 23 bits 52 bits

Example. $-6.5 = -110.1_2 = -1.101 \times 2^2$, so $S=1$, $E=2+127=129=10000001$, mantissa $=101000\ldots0$. The word is $1\ 10000001\ 1010000\ldots0$, which is hex C0D00000.

Floating Point Arithmetic Operation

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. A floating-point number is stored as $(-1)^S \times 1.M \times 2^{E-\text{bias}}$ in the IEEE 754 format.

Key points.

  1. Single precision uses 32 bits: 1 sign, 8 exponent (bias 127) and 23 mantissa bits.
  2. Double precision uses 64 bits: 1 sign, 11 exponent (bias 1023) and 52 mantissa bits.
  3. Addition or subtraction: align the smaller exponent to the larger, add or subtract the mantissas, normalise, then round.
  4. Multiplication: add the exponents (subtract the bias once), multiply the mantissas, normalise, and XOR the signs.
  5. Division: subtract the exponents, divide the mantissas, and normalise.
  6. Example: 1.0 is $0\ 01111111\ 000\ldots0$.

<mark>In IEEE 754 single precision the value is $(-1)^S \times 1.M \times 2^{E-127}$ with 1, 8 and 23 bits.</mark>

Design of Arithmetic Unit

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. The arithmetic unit is the combinational part of the ALU built from full adders, XOR gates and multiplexers to perform add, subtract and other operations.

Key points.

  1. A ripple-carry adder chains $n$ full adders, so its delay grows with $n$.
  2. An adder-subtractor XORs each $B$ bit with a mode line $M$ and feeds $M$ as the first carry-in: $M=0$ adds and $M=1$ subtracts.
  3. A carry-lookahead adder uses generate $G_i=A_iB_i$ and propagate $P_i=A_i \oplus B_i$ to get $C_{i+1}=G_i+P_iC_i$ in parallel, and so is faster.
  4. Multiplexers select the operation and status flags (carry, zero, sign, overflow) are set.

<mark>An adder-subtractor uses XOR gates on B with a mode line that is also the initial carry-in.</mark>

Answer frame. Open with the definition of the adder-subtractor; draw the block diagram below; explain ripple carry and then carry lookahead; close with the flags.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u2-01" viewBox="0 0 467 252" width="467" height="252" role="img" aria-label="Adder-subtractor. B = input B bits, X = XOR gates, FA = chain of full adders, S = sum output, M = mode line (0 add, 1 subtract) also used as carry-in."><style>#dsfig-u2-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u2-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u2-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u2-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u2-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u2-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u2-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u2-01 .t{fill:#16181D;font-weight:500}#dsfig-u2-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u2-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u2-01 .dot{fill:#16181D}#dsfig-u2-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u2-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u2-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u2-01 .ah{fill:#454C5A}#dsfig-u2-01 .ah.hi{fill:#2340B8}#dsfig-u2-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u2-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u2-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u2-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u2-01 .e{stroke:#B1B7C3}html.dark #dsfig-u2-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u2-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u2-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u2-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u2-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u2-01 .t{fill:#E6E8ED}html.dark #dsfig-u2-01 .t.inv{fill:#0F1115}html.dark #dsfig-u2-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u2-01 .dot{fill:#E6E8ED}html.dark #dsfig-u2-01 .ann{fill:#8FA3FF}html.dark #dsfig-u2-01 .lbl{fill:#858D9C}html.dark #dsfig-u2-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u2-01 .ah{fill:#B1B7C3}html.dark #dsfig-u2-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u2-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u2-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u2-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah4" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh4" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M59,40 L148,40" marker-end="url(#ah4)"/><path class="e" d="M184.8,50.5 L280.5,114.4" marker-end="url(#ah4)"/><path class="e" d="M317,126 L406,126" marker-end="url(#ah4)"/><path class="e" d="M51.4,196.8 L156.4,56.8" marker-end="url(#ah4)"/><path class="e" d="M58,206 L278.1,132.6" marker-end="url(#ah4)"/><g class="wl"><rect x="152.2" y="160" width="33.6" height="18" rx="9"/><text class="t" x="169" y="169" dy=".35em" text-anchor="middle">Cin</text></g><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">B</text><circle class="n" cx="169" cy="40" r="18"/><text class="t" x="169" y="40" dy=".35em" text-anchor="middle">X</text><circle class="n" cx="298" cy="126" r="18"/><text class="t" x="298" y="126" dy=".35em" text-anchor="middle">FA</text><circle class="n" cx="427" cy="126" r="18"/><text class="t" x="427" y="126" dy=".35em" text-anchor="middle">S</text><circle class="n" cx="40" cy="212" r="18"/><text class="t" x="40" y="212" dy=".35em" text-anchor="middle">M</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Adder-subtractor. B = input B bits, X = XOR gates, FA = chain of full adders, S = sum output, M = mode line (0 add, 1 subtract) also used as carry-in.</figcaption></figure>

Last-minute revision

  • Two's complement = invert bits and add 1; range $-2^{n-1}$ to $2^{n-1}-1$.
  • $A-B = A + \overline{B} + 1$.
  • Overflow: $C_{n-1} \oplus C_n = 1$.
  • Full adder: $S = A\oplus B\oplus C_{in}$, $C_{out}=AB+C_{in}(A\oplus B)$.
  • Booth: 10 subtract M, 01 add M, 00 and 11 shift only.
  • Restoring division: subtract, and if negative restore and set $Q_0=0$.
  • IEEE single: 1, 8, 23 bits, bias 127; double: 1, 11, 52 bits, bias 1023.
  • Float add: align, add, normalise, round.
  • Carry lookahead: $C_{i+1}=G_i+P_iC_i$.

Memory hooks

  • Two's complement: "flip and add one".
  • Booth: "10 minus, 01 plus, same shift".
  • Overflow: two positives make a negative, or the reverse.
  • Float add: "Align, Add, Normalise, Round" (AANR).

Coverage checklist

  • Addition and Subtraction: no past questions.
  • Tools Compliment Representation: no past questions.
  • Signed Addition and Subtraction: no past questions.
  • Multiplication and division: no past questions.
  • Booths Algorithm: no past questions.
  • Division Operation: no past questions.
  • Floating Point Arithmetic Operation: no past questions.
  • design of Arithmetic unit: no past questions.
Go to where you left off?

Quick Add to Notes

Save questions, your own notes and screenshots into notes filed by unit. It takes a free account.

Create free account

Have an account? Log in