DEV Community: Rohit Dhatrak

Building your own Arithmetic Logic Unit (ALU)

Rohit Dhatrak — Sat, 01 Mar 2025 10:55:15 +0000

Introduction

In this post, we will explore fundamental questions about a computer like why do computers use 1s and 0s? What are the building blocks of a computer? How does a computer perform arithmetic operations? We will do this by constructing our own version of an Arithmetic Logic Unit (ALU) from scratch.

Why does a computer use 1s and 0s?

Binary Number System

Computers use the binary number system (aka base 2 number system). This system consists of only two unique digits: 0 and 1. Thus, all information in a computer is represented using combinations of these two digits. But why just two digits? The answer lies in the nature of the electric circuits that make up a computer. These circuits have only two states: on, which is represented by a 1, and off, which is represented by a 0.

The code snippet below shows how we represent decimal numbers in the binary number system. Notice that with each additional digit, the number of possible combinations doubles. With n digits, the total number of unique numbers that can be represented is 2^n.

// 1 digit: 2 possible combinations
0  // zero
1  // one

// 2 digits: 4 possible combinations
00 // zero
01 // one
10 // two
11 // three

// 3 digits: 8 possible combinations
000 // zero
001 // one
010 // two
011 // three
100 // four
101 // five
110 // six
111 // seven

If you want to learn more about the binary number system you can watch this video by Khan Academy or read more about it here.

Two’s Complement

But how do we represent negative numbers using the binary number system? The two’s complement method is the most commonly used method (also known as radix complement). In this method half of the combinations are used to represent negative numbers.

For example, in a 4-bit binary number system, -5 is represented by calculating 2^4 - 5, which equals 11. In binary, 11 is represented as 1011. To verify, recall that +5 is represented as 0101 in binary. Adding 1011 and 0101 yields 10000. Ignoring the overflow bit, we get 0000, confirming that the representation is correct.

0000 // 0
0001 // 1
0010 // 2
0011 // 3
0100 // 4
0101 // 5
0110 // 6
0111 // 7
1000 // -8
1001 // -7
1010 // -6
1011 // -5
1100 // -4
1101 // -3
1110 // -2
1111 // -1

The code snippet above shows all the possible combinations of signed numbers in a 4-bit binary system.

We can observe the following properties of the two’s complement number system:

All positive numbers begin with 0, and all negative numbers begin with 1. Thus, the most significant bit (MSB) indicates the sign of the number.
In an n-bit system, the total number of possible combinations is 2^n. Since half of the range is used to represent negative numbers, we can represent numbers ranging from -2^(n-1) to 2^(n-1) - 1 (-1 because we have zero as well)
To get the binary representation of -x from the binary representation of x, flip all the bits of x and then add 1 to the result.

The Lego blocks of a computer

A logic gate is a basic building block of digital circuits that performs a specific logical function on one or more binary inputs to produce a single binary output.

Basic Logic Gates

NOT Gate
- Function: Outputs the opposite (inverted) value of the input.
- Truth Table:
```
A | Output
-----------
0 |   1
1 |   0
```

AND Gate

Function: Outputs 1 only if all its inputs are 1.

Truth Table

A | B | Output
---------------
0 | 0 |   0
0 | 1 |   0
1 | 0 |   0
1 | 1 |   1

OR Gate

Function: Outputs 1 if at least one of its inputs is 1.

Truth Table:

A | B | Output
---------------
0 | 0 |   0
0 | 1 |   1
1 | 0 |   1
1 | 1 |   1

XOR

Function: Outputs 1 only if all its inputs are different.

Truth Table:

| A | B | Output |
|---|---|--------|
| 0 | 0 |   0    |
| 0 | 1 |   1    |
| 1 | 0 |   1    |
| 1 | 1 |   0    |

NAND Gate

Function: Outputs 0 only if all its inputs are 1 (the opposite of the AND gate).

Truth Table:

A | B | Output
---------------
0 | 0 |   1
0 | 1 |   1
1 | 0 |   1
1 | 1 |   0

These are just a few of the basic logic gates; there are many more. As we delve deeper, we'll see that these gates form the foundation of a computer, enabling complex operations and computations by combining multiple gates in various configurations.

Among these gates, the NAND gate stands out as a universal gate. This means that any logic gate can be constructed using only NAND gates, making it a powerful and versatile component in digital circuit design.

Here is the HDL code for creating NOT, AND, OR & XOR gates using the NAND gate as a starting point. Additionally, there are 16-bit variants of these gates, which take 16-bit inputs and produce a 16-bit output instead of single-bit outputs. (NOT16, AND16, OR16)

Multiplexer

A multiplexer is a three-input gate that selects between two data inputs, a and b, based on a third input called the sel (selection) bit. The multiplexer outputs the value of a when the selection bit is 0 and the value of b when the selection bit is 1. The truth table & the diagram of a multiplexer is given below.

Truth Table:

| sel | a | b | out |
|-----|---|---|-----|
|  0  | 0 | 0 |  0  |
|  0  | 0 | 1 |  0  |
|  0  | 1 | 0 |  1  |
|  0  | 1 | 1 |  1  |
|  1  | 0 | 0 |  0  |
|  1  | 0 | 1 |  1  |
|  1  | 1 | 0 |  0  |
|  1  | 1 | 1 |  1  |

This functionality allows a multiplexer to act as a simple switch that chooses between two inputs based on the selection bit. You can check the implementation of a Mux using the basic gates that we built earlier. Using the Mux chip we can create a Mux16 chip that will do the same thing but with a 16-bit input.

Half Adder

A half adder is a digital circuit that performs the addition of two single-bit binary numbers. It produces two outputs: the sum bit and the carry bit.

Function:

Sum (S): Represents the sum of the two input bits.
Carry (C): Represents the carry-out bit, which is 1 if the sum exceeds the value that can be represented by a single bit.

Truth Table:

| A | B | Carry (C) | Sum (S) |
|---|---|-----------|---------|
| 0 | 0 |     0     |    0    |
| 0 | 1 |     0     |    1    |
| 1 | 0 |     0     |    1    |
| 1 | 1 |     1     |    0    |

We can observe that the sum and the carry can be computed by using an XOR and AND gate respectively. You can see the implementation of a HalfAdder circuit here.

Full Adder

A full adder is a digital circuit that performs the addition of three binary bits: two significant bits (a & b) and an incoming carry bit (Cin). It produces two outputs: the sum bit and the carry-out bit.

Function:

Sum (S): Represents the sum of the three input bits.
Carry (C): Represents the carry-out bit, which is 1 if the sum exceeds the value that can be represented by a single bit.

Truth Table:

| a | b | Cin | Carry (C) | Sum (S) |
|---|---|-----|-----------|---------|
| 0 | 0 |  0  |     0     |    0    |
| 0 | 0 |  1  |     0     |    1    |
| 0 | 1 |  0  |     0     |    1    |
| 0 | 1 |  1  |     1     |    0    |
| 1 | 0 |  0  |     0     |    1    |
| 1 | 0 |  1  |     1     |    0    |
| 1 | 1 |  0  |     1     |    0    |
| 1 | 1 |  1  |     1     |    1    |

We can calculate the sum using two Half Adder circuits and then OR the two carry’s from the two Half Adders to give us the final carry output. You can take a look at the implementation here.

Add16

Using the Half Adder and Full Adder implemented above we can create a circuit that takes two 16-bit binary numbers and outputs the sum of the two numbers.

You can look at the implementation of an Add16 circuit here.

How does a computer do basic math?

An Arithmetic Logic Unit (ALU) is a fundamental component of a computer's central processing unit (CPU) responsible for performing arithmetic and logic operations. It is a critical part of the CPU and is essential for executing a variety of tasks that the CPU needs to perform.

Our ALU Architecture

The ALU (Arithmetic Logic Unit) receives two 16-bit binary inputs, x and y. Various control pins dictate the operations performed on these inputs before producing the final output. Here is a detailed breakdown of how each control pin influences the process:

zx:
- If zx is 1, set x to 0, regardless of its original value.
zy:
- If zy is 1, set y to 0, regardless of its original value.
nx:
- If nx is 1, negate the value of x (apply bitwise NOT operation to x).
ny:
- If ny is 1, negate the value of y (apply bitwise NOT operation to y).
f:
- If f is 1, compute the sum of x and y (x + y).
- If f is 0, compute the bitwise AND of x and y (x & y).
no:
- If no is 1, negate the result from the f operation (apply bitwise NOT to the output of f).

Finally, the ALU produces the following outputs:

out:
- The result after all specified operations have been applied to x and y.
zr:
- A flag that is set to 1 if the out value is zero; otherwise, it is set to 0.
ng:
- A flag that is set to 1 if the out value is negative (the most significant bit of the 16-bit output is 1); otherwise, it is set to 0.

Truth Table:

Using the 6 control bits (zx, nx, zy, ny, f & no) we can do all the above operations with our two inputs x & y

How to make an ALU?

An Arithmetic Logic Unit (ALU) can be constructed using the basic chips and gates we have created so far. Here’s a detailed explanation of how each step in the ALU works:

// zero the x & y input
Mux16(a= x, b= false, sel= zx, out= zeroXResult);
Mux16(a= y, b= false, sel= zy, out= zeroYResult);

We check if the zx and zy control flags are set. If zx is set to 1, the input x is zeroed. Similarly, if zy is set to 1, the input y is zeroed. This is done using a Mux16 chip, which selects between the original input and zero based on the control flags.

// negate the x & y input?
Not16(in= zeroXResult, out= notX);
Not16(in= zeroYResult, out= notY);
Mux16(a= zeroXResult, b= notX, sel= nx, out= notXResult);
Mux16(a= zeroYResult, b= notY, sel= ny, out= notYResult);

Next, we compute the bitwise NOT of x and y. Depending on the values of the nx and ny control flags, we either keep the original values or use their negated forms. The Mux16 chip is used again to select between the original and negated values.

// compute (out = x + y) or (out = x & y)
And16(a= notXResult, b= notYResult, out= andResult);
Add16(a = notXResult, b = notYResult, out = addResult);
Mux16(a= andResult, b= addResult, sel= f, out= fResult);

We check if the f control flag is set. If f is set to 1 the ALU either computes the sum of x and y otherwise it computes the bitwise AND of x and y. The Mux16 chip selects between the AND result and the addition result.

// negate the output
Not16(in= fResult, out= notFResult);

// out & ng
Mux16(a= fResult, b= notFResult, sel= no, out=out, out[15]= ng, out[0..7]= outFirst8, out[8..15]= outSecond8);

Depending on the no control flag, the ALU either keeps the computed result or negates it. The Mux16 chip selects between the original and negated output. The most significant bit (MSB) of the output is used to determine the sign of the result, setting the ng (negative) flag if the MSB is 1. We also break the output in two parts and store it to use in the next step.

// zr
Or8Way(in= outFirst8, out= zr1);
Or8Way(in= outSecond8, out= zr2);
Or(a= zr1, b= zr2, out= orZr);
Not(in= orZr, out= zr);

To determine if the output is zero, the ALU uses two Or8Way chips to check if any of the bits in the lower and upper halves of the output are 1. If both halves are zero, the zr (zero) flag is set to 1 using an Or and Not gate.

Conclusion

By combining basic logic gates, multiplexers, and adders, we built an ALU—the heart of a CPU. While we have chosen the NAND gate as our fundamental building block, other gates such as NOR or AND-OR-INVERT (AOI) could also serve as a basis for constructing logic circuits. Also while our ALU is capable of computing 64 different functions, we focus on only 18 of these in our implementation. The design prioritizes functionality over efficiency, more advanced techniques like carry lookahead can significantly optimize arithmetic operations, leading to better performance. Since addition is fundamental to computer architectures, such improvements can have a system-wide impact. However, our approach emphasizes a minimalistic ALU design, delegating complex arithmetic operations to system software. This division reflects a common trade-off in computing: balancing hardware complexity with software flexibility. This foundational understanding takes us a step closer to comprehending how low-level hardware functions and interacts with high-level programming, shaping the core of modern computing systems.

Why JavaScript will always need Transpilers and Polyfills

Rohit Dhatrak — Tue, 28 Sep 2021 15:27:18 +0000

This blog post was originally published here .

To understand why we’ll always need transpilers and polyfills let's take a look at Backwards and Forwards compatibility in JavaScript.

Backwards compatibility

Backwards compatibility means that once something is added to the language there won’t be any changes in the future that cause it to become invalid.

Think about this for a second. This assurance is no small thing, right?

We certainly shouldn’t take it for granted. This has a huge impact on decisions involving adding something to the language. Because once it is added we can't remove it just like that.

We are not going to wake up one day and find our code has just stopped running. Because of this assurance we, JavaScript developers can sleep peacefully and it makes choosing JavaScript a safe bet.

But there are some exceptions to this.🙃 JavaScript has a few backwards-incompatible changes. However, the JavaScript committee is very careful in doing so.

They study the code on the web by gathering data from the browsers to get an estimate of the impact. They make the change only if the impact is going to be minimal and if the browsers are willing to take the brunt from the change.

Forwards Compatibility

Forwards compatibility means new syntax would be able to run in an old JavaScript engine. That is if we take some code that was added to the language in 2019 it should be able to run in a JavaScript engine from 2015, 2010 or any previous years.

JavaScript is not forwards compatible.

On the contrary HTML and CSS are forwards compatible but not backwards compatible.

If we take some old HTML or CSS from 2005 it might not run or produce the same results. On the other hand, if we run modern-day HTML or CSS in an old browser it will just skip over the parts it doesn’t recognize, while the rest would be processed accordingly.

This is possible because HTML and CSS are declarative and it is easier to skip over the stuff that is not recognizable. However, just imagine if the JavaScript engine starts to skip stuff that it doesn't recognize we'll get errors and bugs left and right in our code!

We'll have to support some older versions of the browser because everyone doesn't have the latest version. So if we can’t run new code on an old engine should we always stick to an older syntax based on the oldest engine we need to support?

This is where the tools come in.

Transpilers

A transpiler will convert a new syntax to an older syntax.

The most commonly used transpiler is Babel.

For example, consider the following snippet of code.

if (something) {
  let x = 3
  console.log(x)
} else {
  let x = 4
  console.log(x)
}

If we run this in an older version of a browser where let is not defined we'll run into issues. So babel will transpile it to an equivalent older syntax.

var x0, x1
if (something) {
  x0 = 3
  console.log(x0)
} else {
  x1 = 4
  console.log(x1)
}

We can write newer forms of syntax without worrying about compatibility issues in old browsers.

Polyfills

Polyfills (aka shims) are useful when the issue is related to a missing API rather than some new syntax. Let us understand what we mean by this.

Let's assume we want to support an older version of a browser where Array.map() method is not defined.

So to use the method we’ll have to provide our own implementation that will act as if it was already defined.

if (!Array.prototype.map) {
  Array.prototype.map = function (callback) {
    const newArray = []
    for (let i = 0; i < this.length; i++) {
      newArray.push(callback(this[i], i, this))
    }
    return newArray
  }
}

The if statement will check if the map() method is defined. If not then our custom implementation will kick in.

Transpilers like Babel will automatically detect which polyfills are needed in our code but sometimes we might have to do it ourselves.

The above example is just for illustration purposes. When you need to manually define polyfills use a robust and well-tested polyfill from an official library like es-shims.

Conclusion

Since JavaScript is not forwards compatible there will always be a gap between the latest code we can write and the oldest JS engine we need to support.

As developers, we should focus on writing clean and newer syntax that communicates the ideas effectively and let the tools take care of the compatibility.

Shoutout to the YDKJS book series by Kyle Simpson that enabled this blog post.

Time and Space Complexity

Rohit Dhatrak — Thu, 05 Nov 2020 12:05:11 +0000

What is time complexity?

Time Complexity could be used to determine if our algorithm will be able to run in the required amount of time by looking at how the runtime grows according to the input. We don't measure the runtime in seconds as it depends on various factors which we don't want to take into consideration. We are interested in the behaviour of an algorithm for a large number of inputs.

How do we measure time complexity?

Big-O notation gives the upper bound of the time complexity of an algorithm.

Let's say we have a function T(n) which gives the runtime of an algorithm where n is the number of inputs. If we can find a function f(n) which when multiplied by c is greater than T(n) then we can say that f(n) upper bounds T(n).

This can be mathematically represented as T(n) <= f(n). And we write it as O(f(n)).

How To Calculate Big O

i) Break your algorithm into individual operations.
ii) Calculate the no of times each operation repeats.
iii) Add everything together.
iv) Remove the constants multiples.
v) Drop the lower order terms.

We get rid of all the constant multiples and the lower order terms because they don't contribute much for large values of input. We'll see the steps in the examples below.

What are the different time complexities?

1. Constant time

int average(int a, int b) {
    int avg = (a+b)/2;      // occurs once
    return avg;             // occurs once
}

After adding all the values we get :
1 + 1 = 2

In this function, each step occurs once so after adding all the steps we get 2. Which can be written as O(1) because we'll drop all the constant multiples.

Therefore as the input increases, the time taken by the algorithm stays the same.

2. Linear time

int find(int arr[], int key) {
    int n = sizeof(arr);         // 1
    for(int i = 0; i < n; i++) { // n
        if(arr[i] == key)        // 1
            return i;            // 1
    }
    return -1;                   // 1
}

After adding all the values we get :
1 + n * (1 + 1)+1
= 2 + 2n

We multiply the values in the for loop i.e (1 + 1) with no of times the loop occurs i.e n. Because the steps inside the for loop will repeat for n number of times.

By dropping the lower order term 2, we get 2n. Then we will drop the constant multiple 2. So the time complexity is given by O(n).

Therefore as input increases, the time taken by the algorithm increases linearly.

3. Quadratic time

int findDuplicates(int array[]) {
    int n = sizeof(array);                        // 1
    for (int i = 0; i < n; i++){                  // n
        for (int j = 0; j < n; j++){              // n
            if (i !==j && array[i] == array[j]){  // 1
                return i;                         // 1
            }
        }
    }
    return -1;                                    // 1
}

After adding all the values we get :
1 + n * (n * (1 + 1 ) ) + 1
= 2 + 2n²

By dropping the lower order term and the constant multiple we get O(n²).

Therefore as input increases, the time taken by the algorithm increases in a quadratic fashion.

4. Logarithmic time

Log is written as log x y

log 2 8 = 3
You can think of it as how many 2's do we multiply together to get 8. The answer is 3.

Now we'll take a look at binary search. The way this algorithm operates is similar to how we might search for a word in a dictionary. Let's say we open the dictionary somewhere in the middle. If the word we are looking for lies in the left half we ignore the right half and then again split the left half in two.

If we keep on doing this process we'll eventually find the word we are looking for because the words in a dictionary are arranged in alphabetical order. Similarly, if we have an sorted array and we want to look for a value x we can apply binary search.

int binarySearch(int arr[], int x) {

    int l = 0;
    int h = sizeof(arr)-1;

    while (r >= l) {
        int mid = l + (r - l) / 2;

        // If the element is present at the
            // middle itself
            if (arr[mid] == x)
            return mid;

            // If element is smaller than mid, then
            // it can only be present in left subarray
            if (arr[mid] > x)
                h = mid - 1;

            // Else the element can only be present
            // in right subarray
        if (arr[mid]<)x
            l = mid + 1;
    }

    // We reach here when element is not present
    // in array
    return -1;
}

In this algorithm, the amount of data we have to work with is reduced by half with each iteration.

n/2, n/4, n/8,...

Therefore in the worst case, we'll find the element in the last iteration i.e we kept on dividing until only one element was left.

This can be mathematically represented by n/n = 1. The denominator can be represented by a power of 2 as we divided by 2 with every iteration.

Therefore we can write it as n/2^k = 1 where k is the number of times we divided by 2.
∴ n = 2^k

Because k is the number of times we divided by 2, k will give us the number of iterations it took to get the number in the worst possible case.
The equation n = 2^k can be written as k = log2(n). Therefore the time complexity is O(log n).

Therefore as input increases, the time taken by the algorithm increases logarithmically.

Therefore the Time Complexity of a loop is considered as O(logn) if the loop variable is divided or multiplied by a constant amount.

for (int i = 1; i <=n; i *= c) {
    // some O(1) expressions
}
for (int i = n; i > 0; i /= c) {
    // some O(1) expressions
}

Here we can see the different time complexities we discussed above and how they compare to each other. O(1) is the fastest and O(n²) is the slowest.

There are other time complexities as well like O(nlog n), O(cⁿ), O(n!) which we'll cover in the future posts. Until then you can sign up to get notified about new posts.

An interesting thing to note is that O(log n) is slower than O(n) for smaller values. But we don't really care about small values we check for the behaviour of the algorithm when the input is large.

What is Space Complexity?

It is same as time complexity but instead of looking at how much more time our algorithm takes as the input grows we look at how much more space does our algorithm consume when we the input grows.

We often optimize for time over space because usually space is not an issue but we want our algorithms to be faster. However, in scenarios like working with embedded systems where we have a memory constrain, space complexity becomes equally important.

If you liked the post or have any questions/suggestions feel free to reach out on any of the social media platforms.

Originally posted here