### Elements of Computing Systems - Chapter 2 - Understandings

Great book and I am proud to own one!
• Int this chapter, we build the ALU the Arithmetic Logical Unit.
• The ALU is the centerpiece chip that executes all the arithmetic and logical operations performed by the computer.
• Building the ALU functionality is an important step toward understanding how the CPU the Central Processing Unit and the overall computer work.
Let 's see an example first:

• A pair of binary numbers can be added digit by digit from right to left.
• First, we add the two right-most digits, also called the least significant bits (LSB) of the two binary numbers.
• Next, we add the resulting carry bit (which is either 0 or 1) to the sum of the next pair of bits up the significance ladder.
• We continue the process until the two most significant bits (MSB) are added.
• If the last bit-wise addition generates a carry of 1, we can report overflow.
• Computer hardware for binary addition of two n-bit numbers can be built from logic gates designed to calculate the sum of three bits (pair of bits plus carry bit).
• The transfer of the resulting carry bit forward to the addition of the next significant pair of bits can be easily accomplished by proper wiring of the 3-bit adder gates.
Ok, so in order to be able to add binary numbers, first we will have 2 inputs and 2 outputs. This operation will be done by an Half Adder chip.

Here is the Truth Table for the Half Adder:

And here is my implementation:
```CHIP HalfAdder {
IN a, b;    // 1-bit inputs
OUT sum,    // Right bit of a + b
carry;  // Left bit of a + b

PARTS:
Xor(a=a, b=b, out=sum);
And(a=a, b=b, out=carry);
}```

A Full Adder will be needed to add 3 inputs (2 binary inputs from the operation itself and the carry bit..)
Here is the Truth Table for the Full Adder:

And here is my implementation for Full Adder:
```CHIP FullAdder {
IN a, b, c;  // 1-bit inputs
OUT sum,     // Right bit of a + b + c
carry;   // Left bit of a + b + c

PARTS:
Or(a=bar, b=baz, out=carry);
}```

The trick here is that, bar and baz can both never be 1. Only one of them can be 1. If one of them is 1, the carry will be 1 as well..

This is a chip that will make an addition operation on 2 16 bit length bus'. Let 's see the Truth Table:

Well note that Overflow is neither detected, nor handled! Here is my implementation:
```CHIP Add16 {
IN a[16], b[16];
OUT out[16];

PARTS:
}```

16-bit Incrementer
This is a simple but elegant chip:

And here is my implementation:
```CHIP Inc16 {
IN in[16];
OUT out[16];

PARTS:
}```

## Negative Binary Numbers

Let 's take a 4 bit example and calculate all possible values it can represent and their equiavalent values in Decimal system:

Well would 't it be better if we could represent negative numbers? A system called 2's Complement is used in Binary Numbers where Binary Numbers are said to be Signed Binary Numbers.

In this fashion, a negative value is represented by: 2^n - x = - x

With Signed Binary Numbers we will have the following table:

## Computing -x from x

(Which means we can do y - x simply by y + (-x)

Input: x
Output: -x

Idea: 2^n - x = 1 + (2^n - 1) - x

2^n - 1 will always be: 1111111...
1111111.. - x is easy: Flip bits of x (Xor..)
Well now, simply add 1 and you get -x...

Here is an other way (The one that we will use in our ALU implementation).

Remember, this is only when 2's complement is used!