Binary Addition, Subtraction and Overflow

In the previous article we settled on two’s complement for signed numbers. In this one we do arithmetic with it: what happens inside an ALU when it adds two numbers, how subtraction is turned into addition, and how the hardware knows when a result did not fit. That last one, overflow, is behind a large share of the arithmetic bugs you will meet in both software and hardware.

Addition, column by column

Binary addition works like the column addition you learned at school, except that you carry when you reach 2 instead of 10. The rules for one column, including a carry coming in from the right, are:

The rule to remember is $1 + 1 = 10_2$: sum 0, carry 1, just as $9 + 1 = 10$ in decimal. This table is the full adder, and in Module 2 we will build it from gates.

Here is $5 + 3$ in four bits:

  Carry:  0110
          0101   (+5)
        + 0011   (+3)
        ------
          1000   (+8)

Working right to left: bit 0 is $1 + 1 = 0$ carry 1; bit 1 is $0 + 1 + 1 = 0$ carry 1; bit 2 is $1 + 0 + 1 = 0$ carry 1; bit 3 is $0 + 0 + 1 = 1$. The result is 1000, which is 8.

Now try $10 + 7$ in the same four bits:

  Carry:  1110
          1010   (10)
        + 0111   (7)
        ------
        1 0001

The 4-bit result is 0001, which is 1. The true answer is 17, and the fifth bit has fallen off the end. The result did not fit; this is overflow, and we will come back to it.

Subtraction

There is no separate subtractor. To compute $A - B$ the hardware computes $A + (-B)$: take the two’s complement of B (invert and add 1) and add it to A.

Here is $9 - 5$ in eight bits. 9 is 00001001 and 5 is 00000101. Inverting 5 gives 11111010, and adding 1 gives 11111011, which is −5. Now add:

  Carry:  11111000
          00001001   (+9)
        + 11111011   (-5)
        ----------
        1 00000100

Discard the carry out and the 8-bit result is 00000100, which is 4. The adder never knew it was subtracting. The control logic inverted the B inputs and set the initial carry-in to 1, which supplies the “add 1” of the two’s complement for free, and then ran an ordinary addition. This is the reason two’s complement is universal.

Overflow

Overflow means the mathematical result is outside the range the bits can hold. There are two different kinds, and confusing them is a classic mistake.

Unsigned overflow and the carry flag

If the numbers are unsigned, overflow is simply a carry out of the most significant bit. Adding 15 and 1 in four bits:

  Carry:  1111
          1111   (15)
        + 0001   (1)
        ------
        1 0000

The true answer is 16 and the register wrapped to 0. The carry out of the MSB is recorded in the carry flag (C) of the processor’s status register.

Signed overflow and the overflow flag

For two’s complement numbers a carry out of the MSB means nothing by itself. Signed overflow has its own rule: it occurs when the carry into the sign bit differs from the carry out of it. XOR those two carries and a 1 means overflow.

The easier way to see it is that the sign of the result is wrong. Add two positives and get a negative, or add two negatives and get a positive, and something has overflowed. Adding +7 and +1 in four signed bits:

  Carry:  0111
          0111   (+7)
        + 0001   (+1)
        ------
          1000   (-8 in two's complement)

The carry into bit 3 is 1 and the carry out of bit 3 is 0. They differ, so this is signed overflow. The true answer, +8, is outside the range −8 to +7, and the pattern 1000 reads as −8.

Adding numbers of opposite sign can never overflow, since the result is always smaller in magnitude than one of the inputs.

A real CPU updates both the carry flag and the overflow flag (V) on every addition, because it does not know whether your program is treating the registers as signed or unsigned. Unsigned code checks C, signed code checks V, and the hardware is the same.

Ripple carry and carry lookahead

In the column-by-column method, each bit has to wait for the carry from the bit to its right. The carry ripples from the LSB to the MSB, and for a 32- or 64-bit adder that ripple is the slowest path in the circuit. This is the ripple-carry adder, and it is small but slow.

A carry-lookahead adder computes the carries in parallel with extra logic, using more gates to save time. We will build both in Verilog in Module 2 and compare them.

Fixed-point fractions

What about 3.14 or −0.5? The simplest scheme is fixed point: you decide that a certain number of bits are the integer part and the rest are the fraction, with an imaginary binary point between them. In a Q4.4 format there are four integer bits and four fraction bits:

$$b_3 b_2 b_1 b_0 ,., f_{-1} f_{-2} f_{-3} f_{-4}$$

The fraction bits have weights $2^{-1} = 0.5$, $2^{-2} = 0.25$, $2^{-3} = 0.125$ and $2^{-4} = 0.0625$.

To write 6.75 in Q4.4: the integer part 6 is 0110, and the fraction $0.75 = 0.5 + 0.25$ is 1100, so the value is 0110.1100.

Not every decimal fraction is representable. In binary, 0.1 is $0.000110011001\ldots_2$, a repeating fraction, in the same way that 1/3 repeats in decimal. This is why $0.1 + 0.2 \neq 0.3$ in most programming languages. It is not a bug; it is a property of binary.

In hardware, fixed-point addition and subtraction use the ordinary integer adder. The adder does not know where the binary point is; you keep track of that in your design. Multiplication needs a little more care, and we will get to it when we build arithmetic circuits.

Practice Exercise

1. Compute $13 - 6$ in 8-bit two’s complement, showing the addition.
2. Add the 8-bit signed values 01100100 (+100) and 00101000 (+40). Does signed overflow occur? Does unsigned overflow occur?
3. Write 2.375 in Q4.4.

That completes the section on numbers. In the next section we turn to Boolean algebra, the set of rules for writing logic as equations and simplifying it before we build anything.