2.3 Integer Arithmetic, Overflow & Multiplication

Theory: Integer Arithmetic, Overflow & Multiplication

Section 2.2 showed three ways to encode signed integers. Here we see how each one is added and subtracted, how the hardware detects that a result does not fit (overflow), how a single adder circuit does both addition and subtraction, and how a simple sequential multiplier builds a product out of additions and shifts (Null & Lobur, Ch. 2; adder/multiplier hardware as in the lecture).

Signed-Magnitude Addition & Subtraction

Signed magnitude works exactly like pencil-and-paper arithmetic with signs. To compute $A + B$:

1. Same signs: add the magnitudes, and give the result the common sign.
2. Different signs: subtract the smaller magnitude from the larger, and give the result the sign of the larger magnitude.
3. Subtraction $A - B$ is done as $A + (-B)$: flip the sign bit of $B$, then apply rules 1–2.
4. Overflow: if adding magnitudes produces a carry out of the leftmost magnitude bit, the result is too big and is lost. (The sign bit does not take part in the addition, so the carry cannot spill into it.)

Mini-example (8 bits: sign + 7-bit magnitude)

$-46 + (-25)$: signs are equal (both negative), so add the magnitudes:

    0101110   (46)
  + 0011001   (25)
  ---------
    1000111   (71)   no carry out of the magnitude, so no overflow

Attach the sign 1: result $1\,1000111 = -71$ ✓.

Signed magnitude needs extra hardware to compare signs, compare magnitudes, and choose add or subtract. That complexity is why computers prefer complement systems.

One’s Complement Addition (End-Around Carry)

In a complement system, subtraction is turned into addition: $A - B = A + (-B)$, where $-B$ is the complement of $B$. Then:

1. Add the two $n$-bit patterns as ordinary unsigned binary, including the sign bits.
2. If there is a carry out of the MSB, do not throw it away: add it back into the least significant bit (the end-around carry).
3. The result is in one’s complement form (if the sign bit is 1, flip the bits to read its magnitude).

Why the end-around carry? One’s complement represents $-B$ as $(2^n - 1) - B$. Adding gives $A + 2^n - 1 - B$. A carry out means the sum reached $2^n$; dropping it removes $2^n$, leaving $A - B - 1$, so we must add the 1 back.

Advantages: only an adder is needed. Disadvantages: two zeros, and the possible second addition (two-step operation) costs time.

Mini-example

$23 + (-9)$ in 8 bits: $23 = 00010111$, $-9 = 11110110$.

  carry out 1 <-
       0001 0111   (23)
     + 1111 0110   (-9)
     -----------
       0000 1101   (carry out of MSB was 1)
     +         1   (end-around carry)
     -----------
       0000 1110   = 14

Two’s Complement Addition & Subtraction

With two’s complement, all we do is add:

1. Add the two $n$-bit patterns, including sign bits.
2. Discard any carry out of the MSB.
3. Subtraction: $A - B = A + (\text{two's complement of } B) = A + B' + 1$.

Why discarding works: $-B$ is stored as $2^n - B$, so $A + (2^n - B) = (A - B) + 2^n$. The extra $2^n$ is exactly the carry out of bit $n-1$, so dropping it leaves $A - B$.

Mini-example

$48 + (-19)$ in 8 bits: $48 = 00110000$, $-19 = 11101101$.

       0011 0000   (48)
     + 1110 1101   (-19)
     -----------
     1 0001 1101   -> discard the carry -> 0001 1101 = 29

Overflow

Overflow is the error that occurs when the true result is outside the representable range (for 4-bit two’s complement: $-8$ to $+7$). The bits that come out look like a valid number but are wrong.

Overflow rule (two’s complement): look at the most significant bit position. Overflow occurs if and only if the carry into the MSB ≠ the carry out of the MSB. In hardware: $V = C_{\text{in,MSB}} \oplus C_{\text{out,MSB}}$.

Equivalent “sign rule”:

• Adding two numbers of different signs never overflows (the result lies between them).
• Adding two numbers of the same sign overflows exactly when the result has the opposite sign.

A carry out of the MSB is not the same as overflow in two’s complement. $(-4) + (-1) = 1100 + 1111 = 1\,1011$ produces a carry out but the answer $1011 = -5$ is correct. Only the carry-in/carry-out mismatch signals overflow.

Mini-example (4 bits)

$5 + 4$: $0101 + 0100$. At bit 2: $1 + 1 = 0$ carry 1, so the carry into the MSB is 1. At the MSB: $0 + 0 + 1 = 1$, carry out 0. Since $1 \ne 0$: overflow. The pattern $1001$ reads as $-7$, but $5 + 4 = 9$ does not fit in $-8$ to $+7$.

Hardware for Addition and Subtraction

The lecture’s block diagram uses two registers, a complementer, a switch and an adder:

• For addition, the switch passes $B$ unchanged to the adder.
• For subtraction, the switch passes the complement of $B$ (and the adder adds 1 more), so the adder computes $A + B' + 1 = A - B$.
• The result is written back into the A register; the OF flag is set when overflow occurs (1 = overflow, 0 = no overflow).

Gate-level version. The complementer and switch are usually built from XOR gates with one control line $M$:

$M$ is also fed in as the carry-in $C_0$ of the ripple-carry adder, which supplies the “+1” of the two’s complement. The overflow flag is one more XOR on the last two carries: $V = C_{n-1} \oplus C_n$ (carry into vs carry out of the MSB).

  M (0 = add, 1 = subtract) goes to every XOR and is also C0
              |
     B3,M      B2,M      B1,M      B0,M
      XOR       XOR       XOR       XOR
       |  A3     |  A2     |  A1     |  A0
       |  |      |  |      |  |      |  |
      [ FA3 ]<-C3-[ FA2 ]<-C2-[ FA1 ]<-C1-[ FA0 ]<- C0 = M
     |    |          |          |          |
    C4   S3         S2         S1         S0

  V (overflow) = C3 XOR C4

Mini-example

$M = 1$, $A = 0110$ (6), $B = 0011$ (3). XOR outputs: $B \oplus 1111 = 1100$. Adder: $0110 + 1100 + 1 = 1\,0011$ → $S = 0011 = 3$ ✓ ($6 - 3$). $C_3 = 1$, $C_4 = 1$, so $V = 0$.

Multiplication: the Sequential (Shift-and-Add) Multiplier

On paper, binary multiplication is easy because each multiplier bit is 0 or 1: each partial product is either 0 or a shifted copy of the multiplicand.

        0011   (3, multiplicand)
      x 0101   (5, multiplier)
      ------
        0011   bit 0 = 1 -> multiplicand
       0000    bit 1 = 0 -> zero
      0011     bit 2 = 1 -> multiplicand shifted 2
     0000      bit 3 = 0 -> zero
     -------
     0001111   = 15

Shift-and-add algorithm (multiplicand shifts left):

1. Product $\leftarrow 0$.
2. For each multiplier bit, starting from the LSB:
   • if the bit is 1, add the (shifted) multiplicand to the product;
   • shift the multiplicand one place left.
3. After all $n$ bits, the product (up to $2n$ bits) is complete.

Hardware version (the lecture’s sequential multiplier). Instead of shifting the multiplicand left (which needs a $2n$-bit adder), real hardware keeps the multiplicand fixed and shifts the partial product right. Registers:

Each cycle examines one multiplier bit ($Q_0$), possibly adds, then shifts the whole $C\,A\,Q$ chain right: $C \to A_{n-1}$, $A_0 \to Q_{n-1}$, and $Q_0$ falls off (it has been used).

Mini-example

With 4-bit registers, $3 \times 5$ starts with $M = 0011$, $A = 0000$, $Q = 0101$. After 4 cycles $A\,Q = 0000\,1111 = 15$. (The full 8-bit trace is Example 6.)

Worked Examples

    0101110   (46)
  + 0011001   (25)
  ---------
    1000111   (71)

    0101110   (46)
  - 0011001   (25)
  ---------
    0010101   (21)

    1101011   (107)
  + 0011001   (25)
  ---------
  1 0000100

  carry out 1 <-
            0001 0111   (23)
          + 1111 0110   (-9)
          -----------
            0000 1101
          +         1   (end-around carry)
          -----------
            0000 1110   = +14

  carry out 0 <-
            0000 1001   (9)
          + 1110 1000   (-23)
          -----------
            1111 0001

            0011 0000   (48)
          + 1110 1101   (-19)
          -----------
          1 0001 1101

            0001 0011   (19)
          + 1101 0000   (-48)
          -----------
            1110 0011