1. Unsigned arithmetic

Unsigned arithmetic

Unsigned addition

We follow the following 4 (bit addition) rules:

• $1+0=1$
• $0+1=1$
• $0+0=0$
• $1+1=10$

Overflow

Take, a $3$-bit value, say $111$. If we perform $111+001$, we end up at $000$ since the addition has overflowed past the MSB.

$$\begin{array}{r}111\\ +\underline{001}\\ 1000\end{array}$$

Hence, this $1$ value is discarded and we are left with $000$.

A question may specify a $n$-bit system.
**Always** pick `overflow` if you end with a carry-out, such as above.

Unsigned subtraction

We follow the following 4 (bit subtraction) rules:

• $0-0=0$
• $1-0=1$
• $1-1=0$
• $0-1=\text{borrow}$

Before doing unsigned subtraction, always check the magnitudes of the operands.
For example, $001 - 101$, the second operand is larger than the first, hence since we are working with unsigned binary, this operation is invalid.

Unsigned multiplication

To multiply two binary numbers together:

1. Select the number with the least $1$ digits.
2. Split the number into parts. $101\Rightarrow 100\text{ and }001$
3. Multiply each part to the other number.
4. Sum resulting parts.

For example, take $01111\times 10010$.

• The number we first take is $10010$.
• Split it into $10000$ and $00010$.
• Take the other number $01111$ and multiply by the specified power of $2$:
  1. $01111\times 10000=01111<<4=011110000$
  2. $01111\times 00010=01111<<1=000011110$
• Sum the resulting parts: $$\begin{array}{r}011110000\\ +\underline{000011110}\\ 0100001110\end{array}$$ Hence the final answer is $0100001110$.

Unsigned division

Computer systems may opt for short or long division algorithms. Here is an example using long division:

$$\begin{array}{l}001001_2\\ 101\overline{)101101}\\ -\underline{101}\\ 0101\\ -\underline{101}\\ 0\end{array}$$

Each comparison should be justified as you progress through each column:

$$\begin{array}{rl}1& <101_2\\ 10& <101_2\\ 101& \ge 101_2\\ 1& <101_2\\ 10& <101_2\\ 101& \ge 101_2\end{array}$$Link to original

2. Signed-magnitude arithmetic

Signed-magnitude arithmetic

Signed addition

Before can before arithmetic with signed-magnitude, we must find and operate on the magnitude as if it was an unsigned binary number.

• If the signs are the same:
  1. Add magnitude to find resutling mangitude.
  2. Sign bit of result will stay the same.
• If they’re different:
  1. Subtract smaller magitude from larger magnitude.
  2. Use sign of operand with larger magntiude for result.

Signed subtraction

We can reduce the complexity of computing binary subtraction, such as in $a-b$, by considering the second operand as a negative number in an addition, by this we can write it as $a+(-b)$. This is relatively cheap to do, as we only need to flip the sign bit, now we can perform signed-magnitude addition on the two resulting operands.

$$\begin{array}{r}(-2)-(-3)=\\ \\ 10010\\ -\underline{10011}\\ \\ \text{is equivalent to}\\ \\ 10010\\ +\underline{00011}\\ 00001\end{array}$$

Signed multiplication / division

• Multiply or divide magnitudes as signed binary.
• Check whether both operands have the same sign:
  • If they are the same: result has positive sign.
  • If not: result has negative sign.

Link to original

3. Complement arithmetic

Complement arithmetic

Complement addition

Given 1’s or 2’s complement operands, we can perform the same bit operations as we did with unsigned numbers to find the correct result. Although, at the end, we add the carry-out bit to the final result.

$$\begin{array}{r}010100\\ +\underline{110100}\\ 1001010\\ +\underline{1}\\ 001011\end{array}$$

Subtraction

Similarly to signed-magnitude subtraction, we treat the second operand as if it was a negative number. $a-b=a+(-b)$ and perform addition instead.

Overflow

Two’s complement overflow occurs when the carry-in to the most-significant bit is not equal to the carry-out.

$$\begin{array}{r}01101\\ +\underline{00100}\\ 10001\end{array}$$

In this case, the carry-in to the most significant bit is $1$ while the carry-out of the MSB is $0$. Hence we’ve experienced an overflow.

$$\begin{array}{r}01101\\ +\underline{10110}\\ 100011\end{array}$$

In this case, the carry-in to the MSB is the same as the carry-out ($1$). Hence, we just discard the carry-out and get the result $00011$.

Complement multiplication / division

We can take one of two approaches:

• Using a naive approach:
  • Find the magnitude of both operands.
  • Perform the operation as if they were unsigned.
  • Convert result to negative if the operands had different signs.
• Using a specialised algorithm: Booth’s algorithm for two’s complement multiplication These are not on the exam.

Link to original