A continuation of my participation in the amazing Nand2Tetris course, by Noam Nisan and Shimon Schocken, now running on Coursera.

In this course you will build a modern computer system, from the ground up. We’ll take you from constructing elementary logic gates all the way through creating a fully functioning general purpose computer. In the process, you will learn how really computers work, and how they are designed.

If interested, see prior related post [DIY Computer Part 1 The NAND Gate]({% post_url 2016-03-06-diy-computer-nands %}).

A half adder is a chip capable of summing two bits.

``````  111
00010101
01011100
--------
01110001
^---1+1=2 (10 in binary, so write 0 and carry 1)
``````

Lets boil down a single sum operation, so we can build it as a circuit.

From two input bits `a` and `b`, we need to determine two output bits, the `sum`, and the `carry`.

`````` carry-->x
?????a??
?????b??
--------
x<--sum
``````

This function can quite simply be represented as the following truth table, taking in two inputs, and producing two outputs:

``````|   a   |   b   |  sum  | carry |
|   0   |   0   |   0   |   0   |
|   0   |   1   |   1   |   0   |
|   1   |   0   |   1   |   0   |
|   1   |   1   |   0   |   1   |
``````

Two prominant logic chips appear to meet the needs of the Half Adder.

In the case of the previous individual sum operation, we need to go a step further and be able to account for carry `c`, the carry calculated and propagated by the previous operation:

`````` carry-->xc
?????a??
?????b??
--------
x<--sum
``````

This is where a full adder plays an important role, being able to deal with three input bits `a`, `b` and `c`, and like the half adder produces two outputs `sum` and `carry`:

``````|   a   |   b   |   c   |  sum  | carry |
|   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   |
``````

Now we have an individual step of the binary addition defined, thanks to the half and full adders, its just a matter of rinse and repeating by leveraging these chips.

A 16-bit Adder, a chip that takes two 16-bit buses and outputs a single 16-bit bus, therefore could be assembled using 15 Full Adders and a single Half Adder (for the rightmost bit which will never have a carry to worry about).

## Negative Numbers

### Signing bit

A scheme that involves sacrificing a single bit, used to represent positive and negative.

For example, in a three bit representation:

``````000  0
001  1
010  2
011  3
100 -0
101 -1
110 -2
111 -3
``````

While it works, has some disturbing qualities, such as `-0` (wtf), not only does this not make sense, it is wasteful of storage.

### 2’s Complement

A more elegant scheme that proposes to represent negative number `-x` using the positive number `2^n - x`. For example, in a 3-bit representation, `-3` is represented as `8` (2^3) minus `3` which is `5` or `101`.

``````000  0
001  1
010  2
011  3
100 -4 (4)
101 -3 (5)
110 -2 (6)
111 -1 (7)
``````
• positive number range `0...2^[n-1]-1`
• negative number range `-1...-2[n-1]`

Two’s complement has the totally elegant and free benefit of making it very easy to support negative numbers in the existing (Adder) circuits that have been designed.

For example:

``````-2 +
-3
``````

In 2’s complement is really:

``````14 +
13
``````

Which is:

`````` 1110 +
1101
-----
11011
^-----this carried over digit is truncated in binary addition
``````

Without throwing away the carried over digit `11011` is decimal 27, but under binary addition is truncated to `1011` which is decimal 11, which in 2’s complement is `-5` (16 - 11).

### Negation

Given binary value `x`, determine `-x` (in 2s complement). On the surface a 2s complement binary negation function, conceptually appears straight forward. If it is indeed a low hanging fruit, we pickup the power of subtraction, without needing to design new chips/hardware. In other words:

``````y - x = y + (-x)
``````

One proposal involves looking at the 2s complement concept from a slightly different angle:

``````2^n - x = 1 + (2^n - 1) - x
``````

Huh, what does that even achieve? From a binary perspective has some attractive properties.

The value 1 or true is just a bus full of 1’s, for a 4-bit scheme is `1111`, or 6-bits is `111111` and so on. To binary subtract a value from a bus full of 1’s, requires simply bit flipping, like this:

``````11111111 -
10101100
--------
01010011
``````

A complete negation example. For an input of `4` (`0100`), would expect a result of `-4` (`1100` which is `12` in 2s complement).

``````1111 -
0100
----
1011 +
1
----
1100
``````

The `+1` operation is note worthy. A simple shortcut pattern is possible here, where you can flip the bits from right to left, stopping the first time 0 is flipped to 1.

## Arithmetic Logic Unit (ALU)

The ALU is central in the notion of a Central Processing Unit, as originally proposed in the Von Neumann Architecture, and is responsible for computing a function `f` on two inputs, and outputting the result. The function `f` is one from a pre-defined set:

• Arithmetic operations such as integer addition, subtraction, multiplication, division, and so on.
• Logical operations such as And, Or, Xor, and so on.

Carry look ahead. Adder optimisation for reducing the length of the carry daisy chain.