Arithmetic
One of the most basic functions of a computer is to perform calculations. Calculations are performed using arithmetic operations such as addition, subtraction, multiplication, and division. Two keys to understanding how computers perform these operations are that multiplication and division can be performed by repeated addition and subtraction, and that subtraction can be performed using addition.
In this lesson, we’re only going to concern ourselves with integer operations. Recall that integers are whole numbers and their opposites. The core of any computer system works entirely with integers, as floating-point numbers require additional, specialized hardware.
Video Lecture
Addition
One of the most basic arithmetic operations inside a computer is to add two numbers together. An adder circuit is the basic electrical circuit that performs this operation (Figure 1). An adder takes three inputs: two bits that are to be added together, and the carry bit from a previous adder (or 0, if there is no previous adder). The adder has two outputs: the sum of the two bits plus the carry-in, and a carry-out value if the result of the addition is (10)2 or (11)2. Note that the sum output is a single bit, so it can only be 0 (off) or 1 (on). If at least two of the three inputs are 1 (on), then the resulting value is too big to fit into a single bit. For this reason, the carry-out side of the adder is also called the overflow of the circuit, as it indicates that the result was too big to fit into one bit.
An adder can be made using 5 gates, as shown above. The two upper gates are XOR gates, while two AND gates connect to a single OR gate at the bottom to produce the carry-out (Cout) value. This set of gates is logically simple, but it is not the only way to construct an adder. Recall that the NAND and NOR gates are universal gates, so it would be possible to build an adder using only those types of gates.
Table 1 illustrates what happens when we add two numbers together using an adder where the carry-in (Cin) is always zero. If both inputs are 0 (off), then both the sum and carry-out are also 0, since 0 + 0 = 0. If exactly one of the inputs is 1 (on), then the sum is 1 (on). In other words, 0 + 1 = 1, and 1 + 0 = 1. The interesting case happens whenever both inputs are 1: 1 + 1 = 2. However, we cannot fit the number 2 into a single bit, since bits can represent only 0 or 1. Therefore, we set the sum to zero and turn on the carry-out (Cout) bit. In binary, this is how we express the fact that (1)2 + (1)2 = (10)2. The zero in (10)2 is the sum bit, while the 1 is the carry-out bit.
| A | B | S | Cout |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
If we only have 1 adder circuit in our system, then we can only add two numbers. If both numbers are 1, the circuit overflows by setting the carry-out bit to 1, which means that the numbers were too big for us to add properly using the adder. Since the overflow occurs at the number 2, one adder by itself isn’t especially useful: it can tell us that 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, or that 1 + 1 = too big. We don’t really need a computer for that purpose.
However, we can take two adder circuits and put them together. When we wire the circuit this way, the carry-out of the first adder is connected to the carry-in on the second adder. The second adder will then calculate the value of its inputs plus the carry-out from the previous adder. Table 2 illustrates this calculation.
| A | B | Cin | S | Cout |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
Chaining adders together enables us to add binary values of any desired length. If we simply connect the carries of full adder circuits together, the result is called a ripple-carry adder, since the first carry-out must be computed before the next adder’s carry-in will be correct. The carries “ripple” through the calculation, causing a delay from the time the inputs are given to the time that the outputs are correct. More advanced circuits, such as carry-lookahead adders, are typically used to improve performance.
Regardless of the details related to adder type and performance, we can see that it is possible to build an electrical circuit that adds two binary numbers together. Such a circuit is the basic building block for all the other arithmetic operations that a computer can perform.
Subtraction
Recall your days from elementary school, when you learned to perform subtraction by hand. Individual digits would have been taught first (for example, 6 - 3 = 3 or 9 - 1 = 8). Once the class had learned subtraction with individual digits, two digit numbers would have been introduced, followed by numbers with more digits. By way of example, consider the problem:
10 - 9
To perform this subtraction the “long” way by hand, you would first write the 10 above the 9, with the 9 lining up under the 0 in the 10. Your teacher would have then observed that you can’t subtract 9 from 0 (since you hadn’t learned about negative numbers yet), so you would “borrow” the 1 next to it, and subtract 9 from 10 instead, leaving a result of 1. Since you “borrowed” 1 from the 1 in 10, that 1 became a 0, 0 - 0 = 0, and your work was finished.
Of course, your teacher was lying about “borrowing” the 1. In actuality, you stole it. When did you ever give it back?
And why do we keep teaching children to “borrow” numbers in subtraction, anyway?
In this section, we’re going to look at another way to perform subtraction using only addition. The key to making this process work is to use the complement of a digit. There are two kinds of complement to consider: the diminished radix complement, which is simply the maximum possible digit minus the value of the actual digit, and the radix complement, which is the diminished radix complement plus 1.
In binary operations, such as those encountered inside a computer, we generally use the radix complement, since the circuitry to implement this approach is faster and less expensive. However, for the purpose of illustrating how subtraction works, I’m going to use only base 10. When doing complement arithmetic in base 10, I find it easier to use the diminished radix complement, which is the nine’s complement in this case. To get the complement of a digit using nine’s complement, simply subtract that digit from 9. Thus, the nine’s complement of 5 is 4, the nine’s complement of 8 is 1, and so on.
Diminished Radix Complement
Let’s consider how we would perform subtraction using two-digit numbers in base 10, using nine’s complement arithmetic. The first order of business is to state that we have the equivalent of an adder circuit for each digit. We will take both input numbers, and break them into their individual digits, to perform the operation. The leftmost digit will produce a carry-out value (which, even in decimal, will always be a 0 or a 1), while the carry-in value for the rightmost digit is always 0. Consider:
15 - 12
Start by writing the 15 and 12 above each other vertically, like you did in elementary school. Now, instead of subtracting the digits individually, take the nine’s complement of 12. To take the nine’s complement of 12, subtract each digit from 9 independently. 9 - 1 = 8 and 9 - 2 = 7, so the nine’s complement of 12 is 87. We’re going to use addition, so we’re going to add:
15 + 87
When we perform this addition, we start in the one’s column, so 5 + 7 = 12. We write the 2 as the result of the addition in this column, and we carry the 1 to the next column. 1 + 8 + 1 (the 1 from 15, the 8 from 87, and the 1 we carried from the previous column) add up to 10. So we write a 0 as the result of the addition in the tens column, and we have an overflow of 1.
Now, a unique step in diminished radix complement arithmetic (in any number base) is the end-around carry. If the result of the addition produces an overflow, which will be 1 if it occurs, we take the carry-out and add it back to the result. We’ve written our result as 02, so we add the 1 from the carry-out to get a result of 03, or just 3. Hopefully, you can easily see that 15 - 12 = 3, which means that we got the right answer.
But what happens if the carry-out is 0? Well, let’s see a situation where this occurs. Consider:
12 - 15
This time, we take the nine’s complement of 15, which is 84. We add 12 + 84 in the same way. 2 + 4 = 6, so we write 6 in the one’s column, and 1 + 8 = 9, so we write a 9 in the ten’s column, giving us a result of 96, with a carry-out (overflow) of 0. Since the overflow is 0, we do not perform an end-around carry. Instead, we take the nine’s complement of the answer, and we put a minus sign in front of the result.
The nine’s complement of 96 is 03, which we negate to get -3. We can check that 12 - 15 is indeed -3.
Radix Complement
Notice in the nine’s complement example above that we have to perform two additions whenever we have an overflow: the first addition is the original addition, while the second addition performs the end-around carry. The process is the same in binary, only we use the one’s complement instead of the nine’s complement. To perform the end-around carry whenever it is needed, we need a whole separate adder circuit (ripple-carry or carry-lookahead) attached to the output of the first adder circuit (itself ripple-carry or carry-lookahead) if we want to be able to subtraction in one step. This extra circuitry costs money, burns electricity, and has a performance penalty.
We can skip the circuitry for the end-around carry if we use radix complement arithmetic instead. Sticking to our examples using base 10, we instead compute the tens complement of the subtrahend (the number to the right of the - sign in subtraction). Let’s start with:
15 - 12
To get the ten’s complement of 12, we first compute the nine’s complement, then add 1 to that value. So we initially perform the nine’s complement as we did above: 9 - 1 = 8 and 9 - 2 = 7, giving us 87. To get the ten’s complement, we add 1, giving us a value of 88. Now we perform the addition:
15 + 88
Addition is performed in the usual way, from the right to left. 5 + 8 = 13, so we write a 3 in the one’s column and carry the 1 into the ten’s column. 1 + 8 + 1 = 10, so we write a 0 in the ten’s column and overflow the remaining 1.
The difference with radix complement arithmetic is that we do not perform an end-around carry. If the overflow is 1, we simply throw it away. Thus, our answer in this example is 03, or just 3, which is correct. As was the case previously, an overflow of 0 means that we have a negative number. Going back to our second example:
12 - 15
We take the ten’s complement of 15, which begins by taking the nine’s complement: 9 - 1 = 8, 9 - 5 = 4, giving 84. Add 1 to the nine’s complement to get the ten’s complement: 84 + 1 = 85. Now we perform the addition:
12 + 85
5 + 2 = 7, so we write a 7 in the one’s column for the result. There is no carry, so 1 + 8 = 9, and we write the 9 in the ten’s column for the result, giving us a result value of 97. We don’t have an overflow this time, since the result of 1 + 8 does not result in a carry-out.
As we did previously, we need to take the complement of the result and put a minus sign in front of it. However, we need to take the ten’s complement this time. First, compute the nine’s complement: 9 - 9 = 0 and 9 - 7 = 2, giving us 02. Add 1 to get the ten’s complement: 02 + 1 = 03. Place the minus sign to yield -03 or just -3.
In decimal, using the radix complement trades an end-around carry that sometimes happens for doing an extra step (the addition of 1) each time we have to take a complement. For this reason, I find that doing math by hand in base 10 is easier using the diminished radix (nine’s) complement. However, inside a computer, we can design the machine to do all the heavy lifting.
It turns out that a computer can perform a radix complement in base 2 efficiently using a simplified adder circuit that just adds 1 to the diminished radix (one’s) complement. Computation of the one’s complement is simple: just use a NOT gate in front of each bit to “flip” it (0 becomes 1 and 1 becomes 0). Using the radix complement helps to simplify other circuits within the computer, which is why modern computers generally use two’s complement arithmetic.
Multiplication and Division
If we can add and subtract, multiplication and division are easy. Multiplication is simply repeated addition: to multiply 3 by 5, for example, one simply needs to compute the sum of five 3’s: 3 + 3 + 3 + 3 + 3. With a slight efficiency optimization, we could equivalently compute the sum of three 5’s: 5 + 5 + 5, which would require fewer computational cycles and would therefore be faster. It is certainly possible to improve multiplication performance with specialized circuitry, and many computers do have these extra circuits. However, dedicated multiplication circuitry is not strictly necessary. It is instead a performance optimization.
The same reasoning applies to division: we can simply perform repeated subtraction. To compute 17 / 5, keep subtracting 5 until the result is less than 5. Thus, we compute 17 - 5 = 12, 12 - 5 = 7, 7 - 5 = 2. It took 3 operations to get the result to be less than 5, so 17 / 5 = 3. Remember, this is integer arithmetic, so we throw away any remainder, and there is no decimal point!
As a special case, we can easily multiply or divide in units of our number base by shifting the digits left or right. In base 10, we can multiply 10 * 9 by taking 9 and rolling a zero onto the end to get 90. We can undo this operation and compute 90 / 10 by simply shifting 90 one place to the right, dropping the 0 and getting a result of 9. Integer arithmetic rules still apply, so 99 / 10 = 9, and we can perform this operation efficiently by simply dropping the second 9.
Of course, the computer operates in base 2, so shifting operates in powers of 2 instead of powers of 10. A left shift multiplies the number by 2, while a right shift might divide by 2. I say “might” because we might have a signed number. Recall that the leftmost bit is the sign bit, so if we shift that bit to the right and add a zero to the front of the number, we’ll convert a negative number to a positive one. That would definitely not be the same result as dividing by 2. Therefore, most computer hardware distinguishes between a logical right shift that blindly shifts the bits one place to the right and an arithmetic right shift that preserves the sign bit and shifts the remaining bits one place to the right, inserting a 0 after the sign bit. By using arithmetic right shifts, efficient division by two can be implemented for both signed and unsigned numbers.
Notes and References
-
Diagram: InductiveLoad (Wikimedia Commons). Public domain. ↩
