Algorithm3.1.1Add FixedWidth (NDigit) Integers in the Decimal Number System
\(carry_{0} = 0\)

For \(i = 0, \cdots, (N1)\)
sum\(_{i} = (x_{i} + y_{i} + carry_{i})\) % \(10\)
carry\(_{i+1} = (x_{i} + y_{i} + carry_{i}) / 10\)
Computers do arithmetic in the binary number system. ^{ 1 } 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. Consider two twodigit 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.2.3), we describe addition of two decimal integers in Algorithm 3.1.1.
\(carry_{0} = 0\)
For \(i = 0, \cdots, (N1)\)
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 Ndigit 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 Ndigit 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 higherorder digit in the minuend. This is shown in Algorithm 3.1.2.
Subtracting \(y\) from \(x\text{.}\)
\(borrow = 0\)
For \(i = 0, \cdots, (N1)\)
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.
One hexadecimal  Four binary  Decimal 
digit  digits (bits)  equivalent 
\(\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\) 
How many bits are required to store a single decimal digit?
Hint AnswerUsing your code from Exercise 3.1.1.1 invent a code for storing two decimal digits in 32 bits. Using this code, does binary addition produce the correct results?
SolutionDevelop an algorithm for adding fixedwidth integers in the binary number system.
Hint SolutionDevelop an algorithm for adding fixedwidth integers in the hexadecimal number system.
SolutionDevelop an algorithm for subtracting fixedwidth integers in the binary number system.
Hint SolutionDevelop an algorithm for adding fixedwidth integers in the hexadecimal number system.
Solution