The Arithmetic Logic Unit

Overview

The arithmetic logic unit (ALU) is the part of the CPU that calculates. This worksheet builds one up from parts you already know. It starts from the half adder, extends it into a full adder, and chains full adders together to add 4-bit numbers. It then shows how negative numbers are stored, how subtraction is done with the same adder, and how the ALU reports what happened using flags. Work through the tasks in order and use the interactive diagrams to check your thinking.

Learning Objectives

By the end of this lab you will be able to:

Build a full adder from two half adders and an OR gate
Explain how full adders are chained into a ripple-carry adder
Represent positive and negative integers in two’s complement
Subtract by adding the two’s complement
Describe the operations an ALU performs and how one is selected
Interpret the Zero, Negative, Carry and Overflow flags

Concept

The Half Adder worksheet ended with a problem. A half adder adds two bits, but every column of a multi-bit addition except the rightmost may need to add three: the two bits in the column and a carry from the column to its right. A circuit that adds three bits is called a full adder. Put four full adders side by side, passing each carry along to the next, and you can add two 4-bit numbers. Add a way to choose between adding, subtracting and logic operations, and you have an ALU. An ALU takes two inputs, usually called A and B, and an operation select input from the control unit that says which operation to perform. It produces a result and a set of single-bit flags that describe the result, such as whether it was zero.

Tasks

Task 1 - Recap: the half adder

A half adder adds two bits, A and B. It outputs a sum bit from an XOR gate and a carry bit from an AND gate.

S = A \oplus B \qquad\qquad C = A \cdot B

A half adder with A = 1 and B = 1 outputs S = and C = .

In a multi-bit addition, a column may need to add bits: the two bits in that column and the carry from the column to its right.

Task 2 - The full adder

A full adder adds three bits, A, B and a carry in, Cin. It can be built from two half adders and one OR gate.

Half adder 1 adds A and B. Its sum is A XOR B, and its carry is called c1.
Half adder 2 adds that sum to Cin. Its sum is the final sum S, and its carry is called c2.
An OR gate combines the two carries. If either half adder carried, the full adder carries out.

Click A, B and Cin to try all eight combinations. Watch the intermediate values A⊕B, c1 and c2, and check each result against the truth table.

S = A \oplus B \oplus C_{in} \qquad\qquad C_{out} = (A \cdot B) + \big((A \oplus B) \cdot C_{in}\big)

A = 1, B = 0, Cin = 1 gives S = and Cout = .

A = 1, B = 1, Cin = 1 gives S = and Cout = .

A = 0, B = 1, Cin = 0 gives S = and Cout = .

Explain why the OR gate at the end can never receive a 1 from both half adders at the same time.

c1 is 1 only when A and B are both 1, and then A XOR B is 0. Half adder 2 then adds 0 and Cin, which can never carry, so c2 is 0. If c2 is 1, A XOR B must be 1, which means A and B are different, so c1 is 0. The two carries are never both 1.

Task 3 - Chaining full adders

To add two 4-bit numbers, use one full adder per column. Each full adder passes its carry out to the carry in of the full adder on its left. The rightmost full adder has nothing to its right, so its carry in is fixed at 0. This design is called a ripple-carry adder, because the carry ripples from right to left.

Click the bits to set A and B, or use the Try buttons. Then press Show the ripple to slow the carries down.

0101 + 0011 = in binary, which is in denary.

For 1111 + 0001, the four sum bits are and the carry out of FA3 is .

Each stage of this adder takes 2 gate delays to settle once its carry arrives, so a 4-bit ripple-carry adder needs gate delays.

Why does FA3 have to wait for FA0, FA1 and FA2 before its outputs are correct?

FA3 needs its carry in, which comes from FA2. FA2 needs its carry in from FA1, and FA1 needs its carry from FA0. Until the carry has rippled through every stage to its right, FA3 is adding the wrong carry, so its sum and carry out may be wrong.

Task 4 - Negative numbers: two’s complement

So far every bit pattern has meant a positive number. To store negative numbers, computers use two’s complement. In a 4-bit two’s complement number, the leftmost bit has the place value −8 instead of +8. All the other place values stay the same.

−8	4	2	1	Value
0	1	0	1	+5
1	0	1	1	−8 + 2 + 1 = −5
1	1	1	1	−8 + 4 + 2 + 1 = −1
1	0	0	0	−8

A pattern that starts with 1 is negative and a pattern that starts with 0 is zero or positive. With 4 bits this gives a range of −8 to +7.

The wheel below lays all 16 patterns out in a circle. The outer numbers read each pattern as unsigned and the inner numbers read it as signed. Adding moves the pointer clockwise. Try 5 + 3, then 15 + 1 (click the 1111 position first), and watch which dashed boundary the pointer crosses each time.

To negate a two’s complement number (turn +5 into −5, or −5 into +5), invert every bit, then add 1. Try the Negate button on a few values.

+5 = 0101 \;\xrightarrow{\text{invert}}\; 1010 \;\xrightarrow{+1}\; 1011 = -5

In 4-bit two’s complement, 1010 means .

In 4-bit two’s complement, −3 is written as .

In 4-bit two’s complement, −1 is written as .

The largest number 4-bit two’s complement can hold is , and the smallest is .

On the wheel, 5 + 3 gives 1000. Why is that correct as an unsigned answer but wrong as a signed answer?

Unsigned, 1000 is 8, and 5 + 3 = 8, so it is correct. Signed, 1000 is −8, but 5 + 3 should be +8, which is too big for 4-bit two’s complement (the largest value is +7). The pointer crossed the +7/−8 boundary, so the signed answer has overflowed.

Task 5 - Subtracting by adding

Two’s complement means the ALU does not need a separate subtracting circuit. Subtracting B is the same as adding −B, and −B is "invert B, then add 1". The adder can add that extra 1 by setting the carry into its rightmost full adder to 1 instead of 0.

A - B \;=\; A + \overline{B} + 1

Here is 6 − 2 worked through. Any carry out of the leftmost bit is ignored.

   B         = 0010
   invert B  = 1101

     0110      (6)
   + 1101      (B inverted)
   +    1      (carry in)
   -------
   1 0100      ignore the carry out -> 0100 = 4

To work out 7 − 5, the ALU inverts 0101 to get .

0111 + 1010 + 1 = 1 , so 7 − 5 = .

For 3 − 5 the 4-bit result is , which is −2 in two’s complement.

Task 6 - The ALU

An ALU contains an adder and a set of logic circuits side by side. The operation select input, sent by the control unit, chooses which result comes out. The ALU below works on 4-bit values.

Operation	Select code	What it does
ADD	`000`	A + B
SUB	`001`	A + NOT B + 1, which is A − B
AND	`010`	Each result bit is 1 only if both A and B have a 1 in that position
OR	`011`	Each result bit is 1 if A or B has a 1 in that position
XOR	`100`	Each result bit is 1 if A and B differ in that position
NOT A	`101`	Inverts every bit of A (B is ignored)

Choose an operation, then click the bits of A and B to change them.

A = 1100, B = 1010. A AND B = .

A = 1100, B = 1010. A OR B = .

A = 1100, B = 1010. A XOR B = .

A = 1100. NOT A = .

Task 7 - Flags

After every operation the ALU sets four flags. Each flag is a single bit stored in the CPU’s status register. Later instructions can check them, for example to jump only if the last result was zero.

Flag	Name	Set to 1 when
Z	Zero	The result is all zeros
N	Negative	The leftmost bit of the result is 1 (negative if the values are signed)
C	Carry	An addition carried out of the leftmost bit, or a subtraction needed to borrow. Either way, the unsigned answer did not fit.
V	Overflow	The signed answer did not fit, for example two positive numbers added to give a negative result

Some real CPUs use the C flag the other way round for subtraction, setting it when no borrow is needed. This worksheet sets C to 1 when a borrow is needed.

Work out each answer on paper first, then check it on the ALU in Task 6.

0111 + 0001 = . Z = , N = , C = , V = .

1111 + 0001 = . Z = , N = , C = , V = .

0101 − 0101 = . Z = , C = .

0011 − 0101 = . N = , C = .

1111 + 0001 sets C but not V. Explain why, thinking about the unsigned and signed meanings of the inputs.

Unsigned, the sum is 15 + 1 = 16, which does not fit in 4 bits, so there is a carry out and C = 1. Signed, the sum is −1 + 1 = 0, and the result 0000 is exactly right, so there is no signed overflow and V = 0.