Signed Numbers, Add/Subtract & Overflow

Start here. Everything later in the chapter (multiply, divide, floating point) assumes you are fluent with two's complement. Slide 19 — overflow detection — is on your exam.

1. Bits have no meaning until you pick a convention

The bit pattern 1111 is 15 if we agree it's unsigned, and −1 if we agree it's 4-bit two's complement. The bits didn't change — the convention did.

Unsigned binary → decimal

Each position is a power of 2. Add up the columns where a 1 sits.

weight	8	4	2	1
bits	1	0	0	1

$(1001)_2 = 8 + 1 = (9)_{10}$ . With $n$ bits you can hold $0 \ldots 2^n - 1$ .

Decimal → binary (repeated division by 2)

20 ÷ 2 = 10  r 0   ← LSB
10 ÷ 2 =  5  r 0
 5 ÷ 2 =  2  r 1
 2 ÷ 2 =  1  r 0
 1 ÷ 2 =  0  r 1   ← MSB

Read the remainders BOTTOM to TOP:  (20)₁₀ = (10100)₂

2. Two's complement — how computers store negatives

There are other schemes (sign-magnitude), but they waste a pattern on two different zeros. Real computers use two's complement.

The one rule you need: in an

n

-bit two's complement number, the most significant bit carries a NEGATIVE weight. All other columns are normal.

\text{value} = -b_{n-1}\,2^{\,n-1} + b_{n-2}\,2^{\,n-2} + \cdots + b_1 2^1 + b_0 2^0

So for 4 bits the column weights are −8 4 2 1:

Example A — `A = 1111` (4-bit)

MSB is 1 ⇒ it's negative. $-8 + 4 + 2 + 1 = -1$ . A = −1

Example B — `A = 11010` (5-bit, weights −16 8 4 2 1)

$-16 + 8 + 0 + 2 + 0 = -6$ . A = −6

Example C — `B = 0101` (4-bit)

MSB is 0 ⇒ positive, read it normally: $4 + 1 = 5$ . B = +5

3-bit table — memorize the shape, not the numbers:

bits	000	001	010	011	100	101	110	111
value	0	+1	+2	+3	−4	−3	−2	−1

MSB 0 → positive · MSB 1 → negative · exactly one zero · range

-2^{n-1} \ldots 2^{n-1}-1

(one extra negative number).

Negating a number (finding −X)

Flip every bit (1's complement), then add 1.

-X = \overline{X} + 1

B      = 0010   (+2)
flip   = 1101   (1's complement)
add 1  = 1110   (2's complement) = −2   ✔ (−8+4+2 = −2)

3. Sign extension

Widening a signed number (4-bit → 8-bit) must not change its value. Copy the sign bit (MSB) into every new position on the left.

4-bit	value	8-bit	check
`1001`	−7	`1111 1001`	−128+64+32+16+8+1 = −7 ✔
`0101`	+5	`0000 0101`	4+1 = 5 ✔

Padding with zeros only works for positive numbers — for negatives it silently turns −7 into +249.

4. Addition

Plain column addition, carrying as usual. Keep only $n$ bits.

  A:    0011   (+3)
  B:    0010   (+2)
      ------
A+B:    0101   (+5)  ✔

5. Subtraction — there is no subtractor

Hardware only knows how to add. So subtraction is turned into an addition:

A - B = A + (\text{2's complement of } B) = A + \overline{B} + 1

Worked example: A = 0011 (3), B = 0010 (2)

1's complement of B      = 1101
2's complement of B      = 1101 + 1 = 1110   (this is −2)

         A:   0011
  −B (2's):   1110
            -------
             10001
             ↑└──┘
          carry  result = 0001 = +1     ✔ 3 − 2 = 1

The carry out of the top bit is discarded in two's complement arithmetic. A carry-out is not the same thing as overflow.

6. Detecting overflow ★ (slide 19)

Overflow = the true answer is too big to fit in $n$ bits. You detect it by one simple observation:

Overflow has occurred when the result has the “wrong” sign.
Two positives can never legitimately add to a negative; two negatives can never add to a positive.

This is the exact table from the slide — reproduce it and you have the marks:

Operation	Operand A	Operand B	Result indicating overflow
A + B	≥ 0	≥ 0	< 0
A + B	< 0	< 0	≥ 0
A − B	≥ 0	< 0	< 0
A − B	< 0	≥ 0	≥ 0

Why only these four rows? Overflow needs the two things being added to push in the same direction.

Addition is risky only when the operands have the same sign. (+) + (−) always lands between them, so it can never escape the range.
Subtraction $A - B$ is really $A + (-B)$ , which flips B's sign — so it's risky when the operands have opposite signs.

Example — 4-bit, range −8 … +7

  0101   (+5)
+ 0100   (+4)
------
  1001   = −7 ?!    Two positives gave a negative → OVERFLOW.
                     (true answer +9 doesn't fit in 4 bits)

  1000   (−8)
+ 1111   (−1)
------
 10111 → 0111 = +7 ?!  Two negatives gave a positive → OVERFLOW.
                        (true answer −9 doesn't fit)

7. The ALU (Arithmetic and Logic Unit)

The block that actually does this. Inputs A and B, an opcode (function selector) choosing the operation, and outputs the result plus status flags (carry, zero).

Arithmetic: addition, subtraction.
Logical: AND, OR, NOT.

A 1-bit ALU contains a full adder plus multiplexers. A MUX (multiplexer) picks one of its inputs based on a selector line: with $S=0$ a 2-to-1 MUX outputs $I_0$ , with $S=1$ it outputs $I_1$ . The output MUX in the ALU selects between the AND result, the OR result and the adder result — that's how the opcode chooses the operation. The Binvert line inverts B, which (with CarryIn = 1) turns the adder into a subtractor.

A 32-bit ALU is 32 one-bit ALUs chained together: the CarryOut of bit $i$ feeds the CarryIn of bit $i+1$ . This organization is called ripple carry.

Section checklist

Read any two's complement number by making the MSB weight negative.
Negate = flip + 1.
Sign extend by copying the MSB.
$A - B = A + \overline{B} + 1$ , discard the carry-out.
Write the 4-row overflow table from memory.