Chapter 2. — Boolean Arithmetic
This week I will be continuing a review of Building a Modern Computer from First Principles. Last week we learned a little bit about Boolean Logic now let’s check out chapter 2: Boolean Arithmetic.
The Central Processing Unit (CPU) is the electronic circuitry within a computer that executes instructions that make up a computer program. One of the important pieces of the CPU is the Arithmetic Logical Unit (ALU). The ALU is a digital circuit that performs arithmetic and logical operations on binary numbers. Most operations performed by digital computers can be reduced to elementary additions of binary numbers so that is what we are going to focus on today.
What are binary numbers? Most of us are familiar with the decimal system, which is founded on base 10, the binary system is founded on base 2. In the base ten system, we have digits 0–9, we do not have a single-digit numeral for 10. A 10 represents (1 ten and 0 ones), just like 11 represents (1 ten and 1 one). In this system when we need to count to a number one more than nine, we zero out the ones column and add one to the tens column. The next column always represents 10 times the previous column. So what about binary? The binary system has only two digits, 0 and 1. In base 10 we have columns (places) for 1, 10, 100, 100, etc, similarly in base two, there are columns (places) for 2, 4, 8, 16, etc.
So remember when we we tried to count to 10 in base 10, when we got to the 9th digit we had to create a new column (tens) to represent the new number. In binary we have two digits, so when we to try to count to 2 in base 2, we count 0, 1… now there is no single digit that stands for ‘two’ in base-two math. Instead we have to create a new column (twos) to represent the number. Putting a 1 in the twos column and a 0 in the units column. Therefore ‘10’ in binary represents (1 two and 0 ones). A three in base two is (1 two and 1 one) so it is written as ‘11’. A four is written as ‘100’ (we zero out the two’s column and add 1 to the four’s column).
When we are given a certain binary pattern, such as ‘10011’, this represents an integer number.
(10011) two = 1(2⁴) + 0(2³) + 0(2²) + 1(2¹) + 1(2⁰) = 19
We can verify that the calculation above does in fact equal 19, so when we press the keyboard keys labeled ‘1’ and ‘9’ and ‘enter’, the number 19 will be represented in the computer's memory as the binary code 10011. More precisely if the computer happens to be a 32-bit machine, what gets stored in the register is the bit pattern 00000000000000000000000000010011.
How do we add binary numbers? A pair of binary numbers can be added digit by digit from left to right, the same way we add in decimal addition. First we always add the two rightmost digits, also called the least significant bits (LSB) of the two binary numbers. Next, we add the resulting carry bit (which will either be a 0 or 1) to the sum of the next pair of bits up the significance ladder. We continue this process until the two most significant bits (MSB) are added. If the last bitwise addition generates a carry of 1, we report overflow, otherwise the addition completes successfully.
We can see that computer hardware for binary addition of two n-bit numbers can be built from logic gates designed to calculate the sum of three bits (a pair of bits plus the carry bit).
How do we deal with negative numbers in a binary system? The method used today by almost all computers is called the 2’s complement method, also known as the radix complement.
This system has the following properties.
-the system can code a total of 2^n signed numbers, of which the maximal and minimal numbers of are 2^n-1–1 and -2^n-1
-the codes of all positive numbers begin with a 0
-the codes of all negative numbers begin with a 1
-to obtain the code of -x from the code of x, leave all the trailing (least significant) 0’s and the first least significant 1 intact, and flip all the remaining bits (convert 0’s to 1’s and vice versa). An equivalent shortcut, which is easier to implement in hardware, is to flip all the bits of x and add 1 to the the result
A particularly attractive feature of this representation is that addition of any two signed numbers in 2’s complement is exactly the same as addition of positive numbers. The 2’s complement method facilitates the addition of any two signed numbers without requiring special hardware beyond that needed for simple bitwise addition. This implies that a single chip called the ALU can be used to encapsulate all the basic arithmetic and logic performed in hardware.
When designing a new computer system, the question of how much functionality the ALU should deliver is essentially a cost/performance issue. The general rule is that hardware implementations of arithmetic and logical operations are usually more costly but achieve better performance. One could also choose to specify an ALU hardware with limited functionality and then implement those same operations in software.