proj2(review)

2.1 Binary Numbers

(an easy way: choose numbers from high to low)

2.2 Binary Addtion

Half Adder

Full Adder

Multi-bit Adder

Half Adder – Full Adder – Multi-bit Adder – 16-bit adder

2.3 Negative Numbers

① Expression of negative numbers

way1

way2：

前一半的二进制数字（0-7）用来表示正数，后一半的二进制数字（8-15）留作表示负数（eg 表示-3，16-3=13）

② Addtion in 2’s Complement

-2+(-3)=-5,-5的补码就是11（1011）

③ Computing -x ⭐

• Eg：算-4的二进制表达：4=100，1111-0100（1111怎么来的，2的4次方-1=15，15的二进制1111）
• 取反码：1111-0100=1011，求补码：1011+1=1100
• 1100=12，就是4的补码（16-4=12）

具体步骤：

① （2的n次方-1）-x

② 得到的结果+1

③ 即 2的n次方-x = （2的n次方-1）-x +1

2.4 ALU

① The Hack ALU

② The Hack ALU operation

（& == And ，| == Or）

③ example

④ zr,ng(other control bits)

2.5 Project 2 Overview

2.6 code

HalfAdder

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

FullAdder

（不理解为什么有3个abc。但是直接看真值表发现只有1/3个数字是为1，就知道都用or这个方式了）

/**
 * Computes the sum of three bits.
 */
 
CHIP FullAdder {
    IN a, b, c;  
    OUT sum,     
        carry;   

    PARTS:
    Xor(a=a , b=b , out=xorab );
    Xor(a=xorab , b=c , out=sum );
    
    And(a=a , b=b , out=andab );
    Xor(a =a , b =b , out =xor2ab );
    And(a=xor2ab , b=c , out=andcc );
    Or(a=andab , b=andcc , out=carry );
}

Add16

/**
 * 16-bit adder: Adds two 16-bit two's complement values.
 * The most significant carry bit is ignored.
 */
 
CHIP Add16 {
    IN a[16], b[16];
    OUT out[16];

    PARTS:
    HalfAdder(a=a[0] , b=b[0] , sum=out[0] , carry=c0 );
    FullAdder(a=a[1] , b=b[1] , c=c0 , sum=out[1] , carry=c1 );
    FullAdder(a=a[2] , b=b[2] , c=c1, sum=out[2] , carry=c2 );
    FullAdder(a=a[3] , b=b[3] , c=c2 , sum=out[3] , carry=c3 );
    FullAdder(a=a[4] , b=b[4] , c=c3 , sum=out[4] , carry=c4 );
    FullAdder(a=a[5] , b=b[5] , c=c4 , sum=out[5] , carry=c5 );
    FullAdder(a=a[6] , b=b[6] , c=c5 , sum=out[6] , carry=c6 );
    FullAdder(a=a[7] , b=b[7] , c=c6 , sum=out[7] , carry=c7 );
    FullAdder(a=a[8] , b=b[8] , c=c7 , sum=out[8] , carry=c8 );
    FullAdder(a=a[9] , b=b[9] , c=c8 , sum=out[9] , carry=c9 );
    FullAdder(a=a[10] , b=b[10] , c=c9 , sum=out[10] , carry=c10 );
    FullAdder(a=a[11] , b=b[11] , c=c10 , sum=out[11] , carry=c11 );
    FullAdder(a=a[12] , b=b[12] , c=c11 , sum=out[12] , carry=c12 );
    FullAdder(a=a[13] , b=b[13] , c=c12 , sum=out[13] , carry=c13 );
    FullAdder(a=a[14] , b=b[14] , c=c13 , sum=out[14] , carry=c14 );
    FullAdder(a=a[15] , b=b[15] , c=c14 , sum=out[15] , carry=c15 );
}

Inc16

/**
 * 16-bit incrementer:
 * out = in + 1
 */
 
CHIP Inc16 {
    IN in[16];
    OUT out[16];

    PARTS:
    HalfAdder(a=in[0] , b=true , sum=out[0] , carry=c0 );
    FullAdder(a=in[1] , b=false , c=c0 , sum=out[1] , carry=c1 );
    FullAdder(a=in[2] , b=false , c=c1, sum=out[2] , carry=c2 );
    FullAdder(a=in[3] , b=false , c=c2 , sum=out[3] , carry=c3 );
    FullAdder(a=in[4] , b=false , c=c3 , sum=out[4] , carry=c4 );
    FullAdder(a=in[5] , b=false , c=c4 , sum=out[5] , carry=c5 );
    FullAdder(a=in[6] , b=false , c=c5 , sum=out[6] , carry=c6 );
    FullAdder(a=in[7] , b=false , c=c6 , sum=out[7] , carry=c7 );
    FullAdder(a=in[8] , b=false , c=c7 , sum=out[8] , carry=c8 );
    FullAdder(a=in[9] , b=false , c=c8 , sum=out[9] , carry=c9 );
    FullAdder(a=in[10] , b=false , c=c9 , sum=out[10] , carry=c10 );
    FullAdder(a=in[11] , b=false , c=c10 , sum=out[11] , carry=c11 );
    FullAdder(a=in[12] , b=false , c=c11 , sum=out[12] , carry=c12 );
    FullAdder(a=in[13] , b=false , c=c12 , sum=out[13] , carry=c13 );
    FullAdder(a=in[14] , b=false , c=c13 , sum=out[14] , carry=c14 );
    FullAdder(a=in[15] , b=false , c=c14 , sum=out[15] , carry=c15 );   
}

ALU

/**
 * ALU (Arithmetic Logic Unit):
 * Computes out = one of the following functions:
 *                0, 1, -1,
 *                x, y, !x, !y, -x, -y,
 *                x + 1, y + 1, x - 1, y - 1,
 *                x + y, x - y, y - x,
 *                x & y, x | y
 * on the 16-bit inputs x, y,
 * according to the input bits zx, nx, zy, ny, f, no.
 * In addition, computes the two output bits:
 * if (out == 0) zr = 1, else zr = 0
 * if (out < 0)  ng = 1, else ng = 0
 */
 
// Implementation: Manipulates the x and y inputs
// and operates on the resulting values, as follows:
// if (zx == 1) sets x = 0        // 16-bit constant
// if (nx == 1) sets x = !x       // bitwise not
// if (zy == 1) sets y = 0        // 16-bit constant
// if (ny == 1) sets y = !y       // bitwise not
// if (f == 1)  sets out = x + y  // integer 2's complement addition
// if (f == 0)  sets out = x & y  // bitwise and
// if (no == 1) sets out = !out   // bitwise not

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) or (out = x & y)?
        no; // negate the out output?
    OUT 
        out[16], // 16-bit output
        zr,      // if (out == 0) equals 1, else 0
        ng;      // if (out < 0)  equals 1, else 0

    PARTS:    
    // zx
    Mux16(a=x , b=false , sel=zx , out=x1 );
    
    // nx
    Not16(in=x1 , out=notx );
    Mux16(a=x1 , b=notx , sel=nx , out=x2 );
    
    // zy
    Mux16(a=y , b=false , sel=zy , out=y1 );
    
    // ny
    Not16(in=y1 , out=noty );
    Mux16(a=y1 , b=noty , sel=ny , out=y2 );
    
    // f
    Add16(a =x2 , b =y2 , out =add ); //+ 是 按位加 运算add
    And16(a=x2 , b=y2 , out=and ); // & 是 按位与 运算and
    Mux16(a=and , b=add , sel=f , out=l1 );
    
    // no
    Not16(in=l1 , out=l2 );
    Mux16(a=l1, b=l2, sel=no, out=out,out[0..7]=kk1, out[8..15]=kk2, out[15]=kk);
    //  ！！！ kk是精华  ！！！
    
    // zr（if we have Or16Way,we will have a easier way to do.)
    Or8Way(in=kk1, out=zr1);
    Or8Way(in=kk2, out=zr2);
    Or(a=zr1, b=zr2, out=zrNot);
    Not(in=zrNot, out=zr);

    // ng(Unbelievable,marvellous!!!)
    Mux(a=false, b=kk, sel=zrNot, out=ng); 
    }