(click the image to flip the switch)
If we want our computer to be able to add, we had better figure out how to do addition in binary. Fortunately, it's quite simple -- the algorithm is the same as in base-10, but with fewer digits. Example (unsigned):
111 (carry)
7 0111
+ 3 0011
---------------
= 10 1010 (sum)
The key here is the addition table for single binary digits:
So, we can add unsigned numbers, but what about signed ones? If the inputs have the same sign, you can add them, and just keep the sign the same. But when they have opposite signs, for instance: -7 + 5, the unsigned algorithm doesn't work. Example:
111
-7 1111
+ 5 0101
------------
10100 Not correct! Expected -2, got -4
This isn't too surprising -- in decimal we have to use a different algorithm for subtraction too. Although it is not too hard to do binary subtraction (it is very similar to adding), it would be nice to be able to handle positive and negative numbers the same way.
Another problem with signed magnitude is that there are two different ways to write zero: 00000 = "+0" and 10000 = "-0".
Solution: pick a different way of representing negative numbers. A clever idea: Two's complement.
As with signed magnitude, we will use a "sign bit" to tell when a number is negative or positive: 0 = positive, 1 = negative. But to negate a number, we'll do something slightly more complicated:
Examples in six-bit Two's Complement:
17 = 010001 -17 = 101110 + 1 = 101111 4 = 000100 -4 = 111011 + 1 = 111100
An important insight: with two's complement, the unsigned addition algorithm always works correctly regardless of the signs of the input values. Examples in six-bit Two's Complement:
00001
5 = 000101
+ -7 = 111001 (-000111 = 111000 + 1 = 111001)
------ -------
111110
This value is negative, since its leading bit is 1, but what is it the negative of? Take the Two's Complement: -111110 = 000001 + 1 = 000010 = 2. Think for a minute about why this works -- what does adding a number and its complement always yield, and what does adding one to that do?
Most modern computers use the Two's Complement representation for signed integers, rather than the signed magnitude format we discussed originally.
We've seen how to represent a variety of different types of data using only binary numbers, using the digits 0 and 1. Now, as we look at the internals of a computer, the next question is how we might actually perform computations on these values.
Modern electronic computers require two basic building blocks -- wires and switches. A wire carries electricity from place to place within the machine, and switches control which wires the current will flow through. At its most basic, a switch is a device that can be either "open" or "closed". If it is closed, current can flow into the switch and out the other side. If it is open, no current can flow.
(click the image to flip the switch)
The switches in modern computers are called transistors, and they consist of three parts:
By measuring whether the output voltage (emitter) of a switch is high or low, you can distinguish two possible values: High voltage is used to represent "1" and low voltage to represent "0".
The transistors in computers are packed very densely on silicon chips. Here's a rough sketch of how they work.
These transistors are packed by the millions (approaching billions) on a single silicon chip. Moore's law says that the transistor counts grow exponentially.
With switches and wires, we can start to build pieces of circuitry that perform computation. At first, this will be incredibly simple computation, but we can build all the way up to very sophisticated operations.
A computing circuit has a very simple structure: Some bits come in as input, the circuit operates, and then some other bits come out as output. A circuit that takes binary values as inputs and returns binary values as outputs is called a "Boolean" circuit, named after the 19th Century English logician George Boole.
Depending on the relationship between the inputs and the outputs, we can compute different things. Let's look at a few of the most basic computing circuits.
An inverter takes a single bit as input, and returns a single bit as output. If the input bit is 0, the inverter outputs 1, and if the input bit is 1, the inverter outputs 0.
We can specify the behavior of an inverter -- or indeed any digital circuit -- by writing down a table of inputs and the corresponding outputs.
| in | out |
| 0 | 1 |
| 1 | 0 |
Such a table is generally called a "truth table" (you can think of a zero as meaning "false" and a one as meaning "true"). Building an inverter is easy.
More interesting functions can be computed if you have more than one input bit. For instance, this function is called "AND":
| A | B | out |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
This function gets its name from the fact that its output is a one if and only if both its inputs are "1", and it outputs zero otherwise. That is, if A and B are 1's (true), then the output is 1 (true); otherwise it is false.
Another useful function on two inputs is the OR function:
| A | B | out |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Note that this function returns 1 if either of its inputs is 1 (or both).
We have seen that we can describe computations on binary digits using truth tables, and we can build circuits to compute these computations using switches and wires. Building circuits out of switches gets complicated quickly. Ideally, we would like to avoid having to think about the individual switches or transistors for each Boolean circuit we want to build.
Fortunately, once we have figured out how to build the NOT, AND, and OR circuits, we no longer have to think about switches: Any truth table can be turned into a circuit using the AND, OR, and NOT circuits described above as building blocks. These building blocks are often called "gates".
Another useful function returns 1 if its two inputs are equal, and zero otherwise.
| A | B | out |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Take a look at this truth table, and observe when the output is 1. This happens if either of two cases holds:
The overall circuit should output a 1 if either of these is true, and 0 if both of them are false. We can express that using an OR gate.
When you want to design a circuit for something, you generally work like this:
If we can figure out how to do step (3) in particular, we will be able to build circuits for any Boolean function we happen to care about.
Side note: We're talking about these things in terms of circuits, but actually there's no reason this needs to be electrical in nature; you can use pipes instead of wires, and valves instead of switches, and build a computer that uses water to compute. The basic ideas are the same.
Fortunately, there is a simple procedure for converting a truth table, step by step, into a circuit. Here it is, along with a worked example:
| A | B | C | out |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
| A | B | C | out |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Circuit diagrams such as those described above are a good way to get a sense of how a Boolean circuit is put together. However, they are not a very good way to describe a Boolean function to somebody in just text. For this reason, we can also express Boolean functions as formulas.
Here are the rules for a Boolean formula:
A procedure similar to that for creating circuits allows us to create Boolean expressions.
Consider binary addition of two numbers. In all the columns except the first, we are actually adding three bits: the carry from the previous column, and the bits from the two numbers being added. A truth table:
| Ci | A | B | sum | Co |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
Note: Ci is "carry in", the carry from the previous column. Co is "carry out", the carry sent to the next column.
How do you build a circuit for that? There are TWO outputs now. But that's okay: You can treat each output as a separate truth table.
Expression for sum, unsimplified:
(~Ci * ~A * B) + (~Ci * A * ~B) + (Ci * ~A * ~B) + (Ci * A * B)
Expression for Co, unsimplified:
(~Ci * A * B) + (Ci * ~A * B) + (Ci * A * ~B) + (Ci * A * B)
You can turn this directly into a circuit diagram, and it will work. But that's a lot of gates! Each *, +, and ~ takes a gate, which means more switches and wires. How we make these expressions smaller?
AND and OR can be treated like multiplication and addition, in that
you can manipulate them algebraically. Going back to the sum
expression, we can factor ~Ci out of the first two terms, and Ci out
of the second two:
~Ci * ((~A * B) + (A * ~B)) + Ci * ((~A * ~B) + (A * B))
This reduces the number of gates from 17 to 14.
In general, circuit complexity can be reduced by manipulating the Boolean expression for a circuit.
In order to avoid having to talk about switches, we introduced the idea of a gate. Similarly, once we have figured out how to build a digital circuit for some operation, we can give it a label of its own, and ignore the details. This kind of abstraction is a crucial idea in computer science.
The addition circuit we designed has three inputs and two outputs:
+-----+
Cin ---| |-- Cout
A -----| ADD |
B -----| |-- sum
+-----+
This ADD circuit is often called an "adder". If we need to add two numbers with multiple bits, we can do so by building one adder for each column of the addition.
