# ALU

### Arithmetic Logic Unit (ALU)

The Hack ALU computes a fixed set of functions on given two 16-bit inputs, out of which the function can be one of the possible eighteen functions.

We instruct the ALU which function to compute using six input bits, called **control bits** to the selected binary values.

{% hint style="info" %}
Since the overall operation is driven by six control bits, the total number of possible functions that ALU can potientially compute is 2^6 = 64 possible functions.
{% endhint %}

![Abstraction of ALU - Representation](https://1086764272-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F61xaDLg3WD0A24S5G3rN%2Fuploads%2FS9FQDKnMot0TYig98sYf%2Fimg.png?alt=media\&token=6493978c-f876-4f16-9e37-b06780f2182c)

```nand2tetris-hdl
Chip name: ALU
Inputs: x[16], y[16], // Two 16-bit data inputs
        zx, // Zero the x input
        nx, // Negate the x input
        zy, // Zero the y input
        ny, // Negate the y input
        f, // Function code: 1 for Add, 0 for And
        no // Negate the out output

Outputs: out[16], // 16-bit output
                zr, // True iff out=0
                ng // True iff out<0

Function: if zx then x = 0 // 16-bit zero constant
                if nx then x = !x // Bit-wise negation
                if zy then y = 0 // 16-bit zero constant
                if ny then y = !y // Bit-wise negation
                if f then out = x + y // Integer 2's complement addition
                                else out = x & y // Bit-wise And
                if no then out = !out // Bit-wise negation
                if out=0 then zr = 1 else zr = 0 // 16-bit eq. comparison
                if out<0 then ng = 1 else ng = 0 // 16-bit neg. comparison

Comment: Overflow is neither detected nor handled.
```

![Abstraction of ALU - Truth Table with control bits](https://1086764272-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F61xaDLg3WD0A24S5G3rN%2Fuploads%2FaAsCWWXqwfYCZ2LWrgfH%2Fimg.png?alt=media\&token=628d8107-6159-4a4a-a39a-8f5e34e95629)

{% hint style="info" %}
Control bits:

zx -- essentially named as zerox -- states whether x is 0 or not -- if zx = true, then x = 0.

nx -- essentially named as negationx -- states whether x will undergo negation or not -- if nx = true, then x will undergo negation.

zy -- essentially named as zeroy -- states whether y is 0 or not -- if zy = true, then y = 0.

ny -- essentially named as negationy -- states whether y will undergo negation or not -- if ny = true, then y will undergo negation.

f -- essentially named as function -- states whether addition or and function is selected -- if f = true, then execute function x + y ; else x & y

no -- essentially named as negationout -- states whether output will undergo negaton or not -- if no = true, then out will undergo negation.
{% endhint %}

{% hint style="info" %}
Output bits:

While output bits other than **out** is not shown in the truth table, there are two output bits -- zr & ng -- other than out.

zr -- essentially named as **z**e**r**o -- states whether the final output is zero or not. -- if out = 0; zr = true

ng -- essentially named as **n**e**g**ative -- states whether the final output is negative or not. -- if out = negative; ng = true
{% endhint %}

{% hint style="info" %}
Remember:

The nx and ny bits cause negation of x and negation of y respectively when true.

Negation (also known as Bitwise negation) of zero (000...00) is essentially (111...11), the 2's complement code of -1.
{% endhint %}

### Implementation of ALU in HDL

The ALU can be implemented using some of the gates we've learnt earlier.

```nand2tetris-hdl
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, nx
   Mux16(a=x, b=false, sel=zx, out=zerox);
   Not16(in=zerox, out=notx);
   Mux16(a=zerox, b=notx, sel=nx, out=inpx);

   // zy, ny
   Mux16(a=y, b=false, sel=zy, out=zeroy);
   Not16(in=zeroy, out=noty);
   Mux16(a=zeroy, b=noty, sel=ny, out=inpy);

   // f
   Add16(a=inpx, b=inpy, out=addxy);
   And16(a=inpx, b=inpy, out=andxy);
   Mux16(a=andxy, b=addxy, sel=f, out=fxy);

   // no, ng -- ng from Sign Magnitude Representation
   Not16(in=fxy, out=notfxy);
   Mux16(a=fxy, b=notfxy, sel=no, out=out, out[0..7] = pzr1, out[8..15] = pzr2, out[15] = ng);

   // zr
   Or8Way(in=pzr1, out=zr1);
   Or8Way(in=pzr2, out=zr2);
   Or(a=zr1, b=zr2, out=notzr);
   Not(in=notzr, out=zr);
}
```

### Implementation of ALU in Java™

*Similar to the Implementation in HDL*

```java
package CombChips;

import java.util.Arrays;

import Misc.Convert;

class ALU_Design extends Mux16_Gate {
    // since Mux16 is the most used gate in ALU

    protected static int[][] ALU(int[] x, int[] y, int zx, int nx, int zy, int ny, int f, int no) {
        int[] arr_x = Convert.Arrayto16(x);
        int[] arr_y = Convert.Arrayto16(y);
        
        // zx, nx
        int[] zerox = Mux16(arr_x, new int[16], zx);
        int[] notx = Not16_Gate.Not16(zerox);
        int[] inpx = Mux16(zerox, notx, nx);

        // zy, ny
        int[] zeroy = Mux16(arr_y, new int[16], zy);
        int[] noty = Not16_Gate.Not16(zeroy);
        int[] inpy = Mux16(zeroy, noty, ny);

        // f
        int[] addxy = Add16_Gate.Add16(inpx, inpy);
        int[] andxy = And16_Gate.And16(inpx, inpy);
        int[] fxy = Mux16(andxy, addxy, f);

        // no, ng -- ng from Sign magnitude representation
        int[] notfxy = Not16_Gate.Not16(fxy);
        int[] out = Mux16(fxy, notfxy, no);

        int[] pzr1 = Arrays.copyOfRange(out, 0, 7);

        int[] pzr2 = Arrays.copyOfRange(out, 8, 15);

        // zr
        int zr1 = Or8Way_Gate.Or8Way(pzr1);
        int zr2 = Or8Way_Gate.Or8Way(pzr2);
        int notzr = Or_Gate.Or(zr1, zr2);
        int[] zr = new int[1];
        zr[0] = Not(notzr);

        // ng
        int[] ng = new int[1];
        ng[0] = out[out.length-1];

        // final array
        int[][] output = {out, zr, ng};
        return output;

    }
}
```

{% hint style="info" %}
The Most Significant Bit is dropped.
{% endhint %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://gittest2121.gitbook.io/nand2tetris/combinational-chips/alu.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.