dhruv's wiki

# Boolean Arithmetic and the ALU

## Representing Negative Numbers

• Possibility #1: Use most significant bit as +/- sign: not very elegant
• Possibility #2: Use 2's complement: doesn't have the problems of the above approach

## 2's complement

If you want to represent a negative number -x, you just represent it as the positive number 2^n - x, where n is the total number of bits.

Here's how that looks like in a 4-bit binary system:

The range of positive and negative numbers using this approach is:

• Positive numbers: $0\text{ to }2^{(n-1)} - 1$
• Negative numbers: $-1\text{ to }-2^{(n-1)}$

The benefit of using 2's complement is that we get the subtraction operation for free. For example, if we want to calculate 7 - 5, we can represent it as 7 + (-5). These numbers in their binary form (using 2's complement for -5) look like:

  0111
+ 1011
------
0010  (overflown bit thrown away)

0010 in decimal form is 2, which is (7 - 5).

## Computing -x

As seen above, y - x can be calculated using the hardware that does addition (by representing it as y + (-x)), but a hardware unit is needed to compute -x in 2's complement. This can be achieved using a simple mathematical trick:

$$2^{n} - x = 1 + (2^{n} - 1) - x$$

$(2^{n}$ is a binary number that is represented by all 1s. To subtract any number from a binary number with all ones, we just need to flip the bits (pretty cool trick!). So we just flip the bits of x and add a 1 (using the hardware we already have).

For example, if we need to calculate the negative of 4 (which would be 1100 for a 4-bit system).

4 -> 0100

flip the bits
1011

1011
+ 0001
------
1100  -> exactly what we need

!!! tip Adding 1 is a special case. We start from the right most bit, and keep on flipping bits until we reach a 0 which is flipped to 1.

!!! note Key takeaway: We don't need to build any special hardware to handle negative numbers.

## Project 2

• Inc16
• ALU

The carry column resembles an AND gate, and the sum column resembles an XOR gate.

CHIP HalfAdder {
IN a, b;    // 1-bit inputs
OUT sum,    // Right bit of a + b
carry;  // Left bit of a + b

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

The third HalfAdder is not needed, since we're only considering the sum output of the HalfAdder anyway, which follows the XOR logic.

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:
Xor(a=intCarry1, b=intCarry2, out=carry);
}

CHIP Add16 {
IN a[16], b[16];
OUT out[16];

PARTS:
}

## ALU

The Hack ALU computes a fixed set of functions based on the setting of 6 input bits, called control units.

The Hack ALU is designed to compute 18 functions, which are listed below (although, having 6 control bits gives allows the possibility of computing 2^6 functions).

The ALU has 2 output control bits (zr, and ng), which work as follows:

• if out=0 then zr = 1 else zr = 0
• if out<0 then ng = 1 else ng = 0
CHIP ALU {
IN
x[16], y[16],  // 16-bit inputs
zx, // zero the x input?
nx, // negate the x input?
zy, // zero the y input?
ny, // negate the y input?
f,  // compute out = x + y (if 1) or x & y (if 0)
no; // negate the out output?

OUT
out[16], // 16-bit output
zr, // 1 if (out == 0), 0 otherwise
ng; // 1 if (out < 0),  0 otherwise

PARTS:
Mux16(a=x, b=false, sel=zx, out=stage1OutX);
Not16(in=stage1OutX, out=notStage1OutX);
Mux16(a=stage1OutX, b=notStage1OutX, sel=nx, out=stage2OutX);

Mux16(a=y, b=false, sel=zy, out=stage1OutY);
Not16(in=stage1OutY, out=notStage1OutY);
Mux16(a=stage1OutY, b=notStage1OutY, sel=ny, out=stage2OutY);

And16(a=stage2OutX, b=stage2OutY, out=xBitwiseAndY);
Mux16(a=xBitwiseAndY, b=xPlusY, sel=f, out=stage3Out);

Not16(in=stage3Out, out=notStage3Out);
Mux16(a=stage3Out, b=notStage3Out, sel=no, out=out, out[0..7]=zout1, out[8..15]=zout2, out[15]=ng);
//pretty neat! -> output can be fanned out to multiple signals
//in a single line

Or8Way(in=zout1, out=or1);
Or8Way(in=zout2, out=or2);
Or(a=or1, b=or2, out=orOut);
//the above 3 lines are to check if all bits in out are 0
Not(in=orOut, out=zr);
}