# Boolean Arithmetic

###### tags: `computerArchitecture` `boolean Aritehmetic`

[Reference video](https://www.youtube.com/watch?v=Wl53tFc5WYQ&t=834s)

## Helf-adder

Both inputs are off and sum and carry are off.
As we turn them on one at a time Sum beccomes 1.

// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/02/HalfAdder.hdl

/**
 * Computes the sum of two bits.
 */

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);   
}


## Full-adder

With three-bits chaing them together we coudl deel with the larger number.





// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/02/FullAdder.hdl

/**
 * Computes the sum of three bits.
 */

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:
    
    //phase 1
        HalfAdder(a=a, b=b, sum=half1Sum, carry=half1Carry);
    //phase 2
        HalfAdder(a=half1Sum, b=c, sum=sum, carry=falf2Carry);
    //phase 3
        Or(a=half1Carry, b=half1Carry, out=carry);
}

## 16-bits of the half-adder

We need to do is chain together them, a branch of the all fullAdder

// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/02/Adder16.hdl

/**
 * Adds two 16-bit values.
 * The most significant carry bit is ignored.
 */

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

    PARTS:
   // Put you code here:
   FullAdder(a=a[0], b=b[0], c=false, sum=out[0], carry=ful0C);
   FullAdder(a=a[1], b=b[1], c=ful0C, sum=out[1], carry=ful1C);
   FullAdder(a=a[2], b=b[2], c=ful1C, sum=out[2], carry=ful2C);
   FullAdder(a=a[3], b=b[3], c=ful2C, sum=out[3], carry=ful3C);
   FullAdder(a=a[4], b=b[4], c=ful3C, sum=out[4], carry=ful4C);
   FullAdder(a=a[5], b=b[5], c=ful4C, sum=out[5], carry=ful5C);
   FullAdder(a=a[6], b=b[6], c=ful5C, sum=out[6], carry=ful6C);
   FullAdder(a=a[7], b=b[7], c=ful6C, sum=out[7], carry=ful7C);
   FullAdder(a=a[8], b=b[8], c=ful7C, sum=out[8], carry=ful8C);
   FullAdder(a=a[9], b=b[9], c=ful8C, sum=out[9], carry=ful9C);
   FullAdder(a=a[10], b=b[10], c=ful9C, sum=out[10], carry=ful10C);
   FullAdder(a=a[11], b=b[11], c=ful10C, sum=out[11], carry=ful11C);
   FullAdder(a=a[12], b=b[12], c=ful11C, sum=out[12], carry=ful12C);
   FullAdder(a=a[13], b=b[13], c=ful12C, sum=out[13], carry=ful13C);
   FullAdder(a=a[14], b=b[14], c=ful13C, sum=out[14], carry=ful14C);
   FullAdder(a=a[15], b=b[15], c=ful14C, sum=out[15], carry=false);
}

## ALU

### Introduction

The ALU is the first truly complicated piece of memory

The ALU is complicated it compute any one of a number of function

### ALU Diagramming

Hint:
**We need to think about the sequencing**

If we think of the data flow of this chip as going form left to right


z and n flags are mean zero and negative. they will applied first.


f function flag get used and is going to decide whether we're doing, maybe, an addition.

no the gate output flag which is going to decide whether or not to negate the output

### x plus y or y plus x

we're going to need two different components,first we might have a adder, second we might have a 16-bit and

And then, I'm going to use this f flag to select between the results

// if (f == 1)  set out = x + y  // integer 2's complement addition


No flag decide whether or not we're going to negate this output


### ZX

// if (zx == 1) set x = 0        // 16-bit constant


### ZY

// if (zy == 1) set y = 0        // 16-bit constant


### NX

// if (nx == 1) set x = !x       // bitwise not


### NY

// if (ny == 1) set y = !y       // bitwise not


### Tunnel
Lebeled ready X and ready Y that just lets us avoid stretching long wire across the entire schematic in this case .


## ZR(zero) and NG(negative)

// if (out == 0) set zr = 1
// if (out < 0) set ng = 1

### ng

split


Input is taking 16 bit and as output are going to two buses one of them is going to have 15 wire which we're going to ignore.
And then the 16 wire is the one we actually want.


### zr


### Result

#### 0x0138 plus 0x000


#### !(0x0015 plus 0x00F)


HDL

// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/02/ALU.hdl

/**
 * The ALU (Arithmetic Logic Unit).
 * Computes one of the following functions:
 * x+y, x-y, y-x, 0, 1, -1, x, y, -x, -y, !x, !y,
 * x+1, y+1, x-1, y-1, x&y, x|y on two 16-bit inputs, 
 * according to 6 input bits denoted zx,nx,zy,ny,f,no.
 * In addition, the ALU computes two 1-bit outputs:
 * if the ALU output == 0, zr is set to 1; otherwise zr is set to 0;
 * if the ALU output < 0, ng is set to 1; otherwise ng is set to 0.
 */

// 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[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:
    //ZX and ZY flag handling
        Mux16(a=x, b=[0..15]=false, sel=zx, out=xMux);
        Mux16(a=y, b=[0..15]=false, sel=zy, out=yMux);
    //NX and NY flag handling 
        Not16(in=xMux, out=NxNux);
        Mux16(a=xMux, b=NxNux, sel=nx, out=readyX);
        Not16(in=yMux, out=NyNux);
        Mux16(a=yMux, b=NyNux, sel=ny, out=readyY);
    // f control bit handling
        Or16(a=readyX, b=readyY, out=ReadyXorReadyY);
        Add16(a=readyX, b=readyY, out=ReadyXaddReadyY);

        Mux16(a=ReadyXorReadyY, b=ReadyXaddReadyY, sel=f, out=fOut);
    // no control bit flager handling, out, ng flag 
        Not(in=fOut, out=NfOut);
        Mux16(a=fOut, b=NfOut, sel=no, out=out, out[15]=ng, out[0..7]=zrLow, out[0..15]=zrHigh);
     
    // ZR flag handling 
	Or8Way(in=zrLow, out=or1out);
	Or8Way(in=zrHigh, out=or2out);
	Or(a=or1out, b=or2out, out=or3out);
	Not(in=or3out, out=zr);
}