# Boolean Arithmetic

The Elements of Computing Systems

Thu 26th Dec 2019

1. Two’s Complement
3. The Arithmetic Logic Unit
4. Exercises

# Two’s Complement

Two’s complement is a way of representing signed binary numbers that makes signed addition use the same logic as unsigned addition. The most significant bit now represents $-2^n$ instead of $2^n$. For example, 1011 in two’s complement represents -8 + 2 + 1 = -5.

An easy way to convert a number to two’s complement is to flip all the bits and add 1.

We look at three different adders:

• The Half-adder, which adds two bits together, producing a sum and a carry.
• The Full-adder, which adds three bits together, producing a sum and a carry.

A Ripple Carry Adder is an Adder that is build from multiple Full-adders chained together. This is simple, but inefficient as for an n-bit number you have a delay of n cycles as you wait for the carry bit to propegate.

# The Arithmetic Logic Unit

Our ALU will compute a set of functions on two 16 bit numbers. The chosen function will depend on six control bits - leading to $2^6 = 64$ possible different functions, although there are probably only about 18 interesting ones.

Control bit:
zx - zero the x input
nx - negate the x input (after zeroing if requested)
zy - zero the y input
ny - negate the y input (after zeroing if requested)
f  - function, 1: Add, 0: And
no - negate the output


For example, if zx, nx and f were 1, we would:

1. Zero the x input, giving 0000000000000000.
2. Negative it, giving 1111111111111111 = -1.
3. Add y and x, giving y - 1.

This was designed manually, thinking backwards from the list of functions the authors wished to support.

# Exercises

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

sum = XOR(a, b)
carry = AND(a, b)


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

sum = XOR(XOR(a, b), c)
carry = OR(AND(a, b), AND(b, c), AND(a, c))


Looking at answers on the internet, most people combined two Half-adders here. Wikipedia on the other hand has the same logic for the sum, but uses one fewer AND gates on the carry by ANDing with XOR(a, b) instead (src).

CHIP Add16 {
IN a, b;
OUT out;

PARTS:
// ...
}


And for the Incrementer (saving mostly so I remember the syntax):

CHIP Inc16 {
IN in;
OUT out;

PARTS:
}


## The ALU

For the ALU it seems wise to create a new block that applies the “maybe zero, maybe negate” logic.

A chip can have multiple out wires (which is useful for the “is result zero” and “is result negative” flags).

Extend turns 0 into 0000000000000000 and 1 into 1111111111111111:

CHIP Extend {
IN  in;      // bit to extend
OUT out; // 16-bit output

PARTS:
Mux16(a=false, b=true, sel=in, out=out);
}


CondZero conditionally zeroes a value:

CHIP CondZero {
IN
in,  // 16-bit input
z;      // zero the input?

OUT
out; // 16-bit output

PARTS:
Not(in=z, out=notz);
Extend(in=notz, out=notz16);
And16(a=in, b=notz16, out=out);
}


Actually thinking about it, I could get rid of Extend and just do:

    Mux16(a=true, b=false, sel=z, out=mask);


CondNeg conditionally negates a value:

CHIP CondNeg {
IN
in,  // 16-bit input
n;      // negate the input?

OUT
out; // 16-bit output

PARTS:
Not16(in=in, out=notin);
Mux16(a=in, b=notin, sel=n, out=out);
}


IsZero checks if a value is zero:

CHIP IsZero {
IN  in;
OUT out;

PARTS:
Or(a=in, b=in, out=a);
Or(a=in, b=in, out=b);
Or(a=in, b=in, out=c);
Or(a=in, b=in, out=d);
Or(a=in, b=in, out=e);
Or(a=in, b=in, out=f);
Or(a=in, b=in, out=g);
Or(a=in, b=in, out=h);

Or(a=a, b=b, out=i);
Or(a=c, b=d, out=j);
Or(a=e, b=f, out=k);
Or(a=g, b=h, out=l);

Or(a=i, b=j, out=m);
Or(a=l, b=l, out=n);

Or(a=m, b=n, out=o);
Not(in=o, out=out);
}


And putting this all together we can construct our ALU:

// Implementation: the ALU logic manipulates the x and y inputs
// and operates on the resulting values, as follows:
// if (zx == 1) set x = 0        // 16-bit constant
// if (nx == 1) set x = !x       // bitwise not
// if (zy == 1) set y = 0        // 16-bit constant
// if (ny == 1) set y = !y       // bitwise not
// if (f == 1)  set out = x + y  // integer 2's complement addition
// if (f == 0)  set out = x & y  // bitwise and
// if (no == 1) set out = !out   // bitwise not
// if (out == 0) set zr = 1
// if (out < 0) set ng = 1

CHIP ALU {
IN
x, y,  // 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-bit output
zr, // 1 if (out == 0), 0 otherwise
ng; // 1 if (out < 0),  0 otherwise

PARTS:
CondZero(in=x, z=zx, out=x1);
CondZero(in=y, z=zy, out=y1);

CondNeg(in=x1, n=nx, out=x2);
CondNeg(in=y1, n=ny, out=y2);

And16(a=x2, b=y2, out=and);