Computer Arithmetic

Arithmetic hardware is an algorithm made physical: registers hold the current state, an adder performs one transformation, a shifter aligns partial results, and a controller repeats the correct microoperation. The same method explains addition, multiplication, and division.

Signed Number Representations

For an $n$-bit sign-magnitude number, the most significant bit is the sign and the remaining $n-1$ bits store the magnitude. Thus 0 0101 is $+5$ and 1 0101 is $-5$. There are two encodings of zero.

For an $n$-bit two’s-complement number, the range is

Negation means complementing every bit and adding one. In 8 bits, $+13=\mathtt{00001101}$ and $-13=\mathtt{11110011}$. Two’s complement has one zero, uses the same adder for signed and unsigned addition, and is therefore the usual machine representation.

For addition, $V=C_{n-1}\oplus C_n$, the XOR of the carry into and out of the sign position. Carry and overflow answer different questions: 11111111 + 1 has unsigned carry, while 01111111 + 1 has signed overflow.

Sign-Magnitude Addition and Subtraction

Let $A_s,B_s$ be the sign bits and $A_m,B_m$ the magnitudes. Convert subtraction into addition by toggling the sign of the second operand:

Example with one sign bit and four magnitude bits:

• 0 1001 + 1 0101 means $+9+(-5)$. Unequal signs select magnitude subtraction: $1001-0101=0100$, so the result is 0 0100 or $+4$.
• 1 0111 - 0 0101 means $-7+(-5)$. Equal effective signs select addition: $0111+0101=1100$, so the result is 1 1100 or $-12$.

Unsigned Add-and-Shift Multiplication

The pencil-and-paper product

          1011   (11)
        × 1101   (13)
        ------
          1011
         0000
        1011
       1011
       --------
       10001111  (143)

adds the multiplicand wherever a multiplier bit is one. Hardware reuses one adder:

1. Clear accumulator $A$ and load multiplier $Q$, multiplicand $M$, and count $n$.
2. If $Q_0=1$, perform $A\leftarrow A+M$.
3. Shift the combined pair $AQ$ right once.
4. Decrement the count; repeat until zero.

For $M=1011$ and $Q=1101$, the combined contents progress through four add/shift iterations and finish at $AQ=1000\,1111_2=143_{10}$.

Booth Multiplication

Booth’s algorithm multiplies signed two’s-complement numbers and compresses runs of ones. Append one bit $Q_{-1}=0$, examine $(Q_0,Q_{-1})$, then perform an arithmetic right shift of the combined $AQ Q_{-1}$.

Worked example: $(-9)(-13)=117$

Use five-bit two’s-complement operands: $M=-9=\mathtt{10111}$ and initially $A=\mathtt{00000}$, $Q=-13=\mathtt{10011}$, $Q_{-1}=0$.

The product is the ten-bit value $AQ=\mathtt{0001110101}_2=117_{10}$. Arithmetic shift is essential because it replicates the sign of $A$.

Combinational Array Multiplication

An array multiplier generates every partial product in parallel with AND gates and sums aligned columns with a regular adder array.

A $j$-bit by $k$-bit unsigned array requires $jk$ AND gates for partial products and can be organized with $(j-1)$ $k$-bit adders. The product width is $j+k$ bits. A $4\times3$ array therefore uses 12 AND gates and two 4-bit adder rows, producing a seven-bit product.

Unsigned Division

For dividend $Q$, divisor $M$, quotient $Q_\text{out}$, and remainder $A$,

Both standard algorithms align the next dividend bit by shifting the combined $AQ$ register left.

Restoring division

Each cycle shifts left, tentatively subtracts $M$, and restores the old remainder when the result is negative:

1. $(A,Q)\leftarrow\operatorname{shl}(A,Q)$.
2. $A\leftarrow A-M$.
3. If $A<0$, set $Q_0\leftarrow0$ and restore $A\leftarrow A+M$; otherwise set $Q_0\leftarrow1$.

Non-restoring division

Avoid the immediate restoration. If the previous partial remainder is nonnegative, shift and subtract; if it is negative, shift and add. Set the quotient bit from the new sign. After the final cycle, add $M$ once if $A<0$.

Worked example: $11/3$

Using $Q=\mathtt{1011}$ and $M=\mathtt{0011}$:

Thus quotient $Q=\mathtt{0011}=3$ and remainder $A=\mathtt{00010}=2$, confirming $11=3(3)+2$. Non-restoring division reaches the same result with partial remainders 11110, 11111, 00010, and 00010; the first two negative states avoid two immediate restore operations.

Choosing an Arithmetic Organization

Check Your Understanding

1. Why can C=1 while V=0, and vice versa?
2. Trace 0 0110 - 1 0011 in sign-magnitude representation.
3. Which Booth action corresponds to pair 01?
4. Why must the combined register shift left during division but right during add-and-shift multiplication?
5. For $13/4$, what quotient and remainder must a correct divider produce?