Boolean Arithmetic and the ALU

This week we continue from last week’s post and dive into part 2 of the Build a Modern Computer from First Principles course. This week will cover the background needed to understand and complete Project 2 next week.

Binary Numbers

Contrary to our base-10 number system (which uses 10 as the base for counting), binary numbers use a base-2 system. So, we have two digits (0, 1) to use in this system. In a 4-bit number, we have the following numbers (represented in decimal form as well for reference). For a 4-bit binary set, we have 0, 1, 2,…, 15, or 0, 1, 2, …, 2ⁿ -1.

To go from decimal to binary, we can use the same formula we use in decimal numbers.

678 = 6 x 10² + 7 x 10¹ + 8 x 10⁰

101 = 1 x 2² + 0 x 2¹ + 1 x 2⁰ = 5

To go from binary to decimal, we use the power of 2s. For example:

98 -> What is the largest power of 2 that can go into 98? 2⁶ = 64 The next largest? 2⁵ = 32. And so on.

98 -> 0 x 2⁷ + 1 x 2⁶ + 1 x 2⁵ + 0 x 2⁴ + 0 x 2³ + 0 x 2² + 1 x 2¹ + 0 x 2⁰

98 -> 01100010

Binary Addition

Also similar to our decimal addition, binary addition has carry values if greater than 1. For example:

 01101101
+01011100
---------
 11001001

If we exceed the word size, we would have a carry that is bigger than the current word size (in this case, 8 bits) and the result will not be accurate:

 01101101
+11011100
---------
101001001

Negative Numbers

When we add negative numbers there are a few systems that could be used. For instance, you could say that half of your numbers with a 0 in the Most Significant Place could be positive and the numbers with a 1 in the Most Significant Place could be negative numbers. Here is an example of that using 4 bit numbers.

But that leads to a lot of problems, because then you have - 0. And we have learned that 0 and - 0 are equivalent. So that is a less than ideal solution.

But, if we used the two’s complement table for the negative numbers, it works really well.

2’s Complement

Let us walk through how this works. If we have a normal addition of negative numbers problem, such as:

(-2)
+
(-4)
----

If we convert these signed numbers into their counterparts using the 2’s complement table above, we get:

14
+
12
----

And if we take the binary equivalents, we get:

 1110
+
 1100
-----
10010

Which is bigger than the word size we are working with because of the 1 carry in the Most Significant Place (farthest left). If we drop the 1, because the word size is too large, we get 0010, which equals 2, which is the correct answer to the problem.

🤯

We can add negative numbers already because the system is built into our binary system using the 2’s complement table.

Flip a number’s sign (positive/negative)

If we want to flip a number negative (or the opposite), it is as simple as flipping each place in the binary number and adding 1.

For example:

1101 -> -3

0010 + 1 = 0011 -> 3

🤯

Arithmetic Logic Unit

While all of the chips represented up until this point are generic and can be found in any computer system, the Hack chip, or ALU chip is unique to this course. It has been chosen to deal only with integer numbers (…, -1, 0, 1, …).

The 18 functions it will be able to compute when correctly coded in project 2, will be as follows with two 16 bit inputs and one 16 bit outputs:

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, and x|y

Summary

This chapter/part dealt with binary numbers, adding binary numbers, negative binary numbers, and the ALU. Next week we will build 5 chips for Project 2 before moving on to part 3 where we will start dealing with memory. Thanks for joining me!