Other Number Systems
Most computer architectures provide arithmetic instructions in other number systems, but these are somewhat specialized. We will not consider them in this book.
Computers do arithmetic in the binary number system. The operations are really quite easy to understand if you recall all the details of performing arithmetic in the decimal number system by hand. Since most people do addition on a calculator these days, let us review all the steps required when doing it by hand. This discussion will be followed by exercises asking you to develop the algorithms to perform addition and subtraction in binary and in hexadecimal.
Most computer architectures provide arithmetic instructions in other number systems, but these are somewhat specialized. We will not consider them in this book.
Consider two two-digit numbers, \(x = 67\) and \(y = 79\text{.}\) Adding these by hand on paper would look something like:
\(1\) | \(1\) | \(\longleftarrow\) | carries |
\(\) | \(67\) | \(\longleftarrow\) | \(x\) |
\(+\) | \(79\) | \(\longleftarrow\) | \(y\) |
\(\) | \(46\) | \(\longleftarrow\) | sum |
We start by working from the right, adding the two decimal digits in the ones place. 7 + 9 exceeds 10 by 6. We show this by placing a 6 in the ones place in the sum and carrying a 1 to the tens place. Next we add the three decimal digits in the tens place, 1 (the carry into the tens place from the ones place) + 6 + 7. The sum of these three digits exceeds 10 by 4, which we show by placing a 4 in the tens place in the sum and recording the fact that there is an ultimate carry of one. Recall that we had decided to use only two digits, so there is no hundreds place. Using the notation of Equation (2.3.3), we describe addition of two decimal integers in Algorithm 3.1.1.
\(carry_{0} = 0\)
For \(i = 0, \cdots, (N-1)\)
sum\(_{i} = (x_{i} + y_{i} + carry_{i})\) % \(10\)
carry\(_{i+1} = (x_{i} + y_{i} + carry_{i}) / 10\)
Note that:
Algorithm 3.1.1 works because we use a positional notation when writing numbers—a digit one place to the left counts ten times more.
Carry from the current position one place to the left is always 0 or 1.
The reason we use 10 in the /
and %
operations is that there are exactly ten digits in the decimal number system: 0, 1, 2,…, 9.
Since we are working in an N-digit system, we must restrict our result to N digits. The final carry, \(carry_{N}\text{,}\) is either \(0\) or \(1\) and is part of the result, along with the N-digit sum.
Let us now turn to the subtraction operation. As you recall from subtraction in the decimal number system, you must sometimes borrow from the next higher-order digit in the minuend. This is shown in Algorithm 3.1.2.
Subtracting \(y\) from \(x\text{.}\)
\(borrow = 0\)
For \(i = 0, \cdots, (N-1)\)
If \(y_{i} \le x_{i}\)
difference\(_{i} = x_{i} - y_{i}\)
Else
\(j = i + 1\)
While \((x_{j} = 0)\) and \((j \lt N)\)
\(j = j + 1\)
If \(j = N\)
\(borrow = 1\)
\(j = j - 1\)
\(x_{j} = x_{j} + 10\)
While \(j \gt i\)
\(x_{j} = x_{j} - 1 \)
\(j = j - 1\)
\(x_{j} = x_{j} + 10\)
difference\(_{i} = x_{i} - y_{i}\)
This algorithm is not nearly as complicated as it first looks. When you do subtraction on paper, you do all these things automatically.
When adding and subtracting in the decimal system you are used to dealing with carry and borrow “in your head,” but that may not be as intuitive for you in the binary and hexadecimal systems. You should memorize Table 3.1.3, which will help you to work in these other number systems, which you are asked to do in Exercises 3.2.1–3.2.6 following this section.
One Hexadecimal | Four Binary | Unsigned |
Digit | Digits (bits) | Decimal |
\(\hex{0}\) | \(\binary{0000}\) | \(0\) |
\(\hex{1}\) | \(\binary{0001}\) | \(1\) |
\(\hex{2}\) | \(\binary{0010}\) | \(2\) |
\(\hex{3}\) | \(\binary{0011}\) | \(3\) |
\(\hex{4}\) | \(\binary{0100}\) | \(4\) |
\(\hex{5}\) | \(\binary{0101}\) | \(5\) |
\(\hex{6}\) | \(\binary{0110}\) | \(6\) |
\(\hex{7}\) | \(\binary{0111}\) | \(7\) |
\(\hex{8}\) | \(\binary{1000}\) | \(8\) |
\(\hex{9}\) | \(\binary{1001}\) | \(9\) |
\(\hex{a}\) | \(\binary{1010}\) | \(10\) |
\(\hex{b}\) | \(\binary{1011}\) | \(11\) |
\(\hex{c}\) | \(\binary{1100}\) | \(12\) |
\(\hex{d}\) | \(\binary{1101}\) | \(13\) |
\(\hex{e}\) | \(\binary{1110}\) | \(14\) |
\(\hex{f}\) | \(\binary{1111}\) | \(15\) |