4.

[Top] [Next] [Prev]

A.3 Binary Arithmetic Operations

We examine the arithmetic operations in the binary number system next.

A.3.1 Addition in Positional Notation

Let's begin by reviewing how addition works in the base 10 positional number system. Consider the addition of 95 and 16 to yield 111:

The numbers are added column by column, one position at a time. Should the column sum exceed 9, the largest digit that can be represented in base 10, we must generate a carry-out to the next higher-order position.

You are familiar with a shorthand method for addition in positional notation. You proceed column by column, from right to left. 5 + 6 = 11, which is written as a sum of 1 with a carry of 1 to the next column. The carry represents an excess quantity that is too big to be represented in a single column. It is then added to the column sum of the next higher position. In the example, 1 + 9 + 1 = 11, which again is represented as a column sum of 1 with a carry of 1. Since there are no additional column sums to be formed, the final carry-out is written as part of the sum. This process, as illustrated by the example, is summarized below:

The same process applies to addition in any base. Next, we will see how addition is applied to base 2.

Addition in Base 2 In the binary number system, we have the following addition table:

Let's illustrate addition in binary with an example. Consider the addition of 1012 and 112 to yield 10002 (510 + 310 = 810):

The step-by-step process is shown at the right, the shorthand method at the left. In longhand, the columns are added up individually. If the column quantity cannot be represented, it must "carry out" a power of two to the next higher column.

Since 102 in the sum's ones column cannot be represented directly, we must add to the next higher column, leaving the 0 behind. The twos column undergoes a similar carry-out: 1 + 1 yields 0 with a carry of 1 to the fours column. This, in turn, cascades to the eights column: 1 + 1 again yields 0 with a carry-out of 1.

It is much easier to work with the shorthand method, of course. We proceed from right to left, adding one column at a time. Beginning with the ones column, 1 + 1 = 0 with a carry of 1 to the twos column. In the twos column, we add the carry of 1 + 0 + 1 = 0 with a carry of 1 to the fours column. Continuing with the fours column, the carry-in of 1 plus 1 is 0 with a carry-out of 1 to the eights column. This results in the final sum, 10002.

As another example, let us look at the addition of 9510 and 1610, but this time in binary:

9510 maps into 10111112, while 1610 is equivalent to 100002. In adding, we work from the rightmost column to the left. In the first column, the sum is 1, as it is in columns two, three, and four. In the fifth column, two 1's are being summed, yielding 0 with a carry of 1. This leads to a sum in the sixth column of 1. The final column also sums to 1. You should verify that 11011112 = 11110.

A.3.2 Subtraction in Positional Notation

Let's review the process of subtraction in base 10. Then we will show how the process applies in base 2.

To illustrate, consider the subtraction of 1610 from 9510 to yield 7910:

The longhand method is shown at the right, the shorthand at the left. At the right, the numbers are rearranged into the positional notation. If the digit to be subtracted is larger than the digit it is being subtracted from, we must borrow from the next higher position to the left. A 10 is subtracted from this column and added back to the original column. This borrowing guarantees that the subtraction can now proceed in the ones column.

Let's start by looking at the example in its long form at the right. Starting with the ones column, 5 is smaller than 6, so we must move 10 units from the tens position to the ones position. Now we can subtract 6 from the resulting 15 to yield 9. For the next column, we subtract 1 from the remaining 8 to obtain 7 in the tens position.

Looking at the shorthand form, since 5 is less than 6, we borrow from the tens column to form 15. 15 - 6 = 9. For the tens column, we subtract 1 from 8 to get 7. So the result is 79. Obviously, the process of borrowing can cascade from right to left in much the same way that carries can propagate.

Subtraction in Base 2 Subtraction in base 2 is much like subtraction in base 10, except that the borrowing process moves two from a higher-order column to a lower-order column. If a column subtraction cannot proceed without yielding a negative result, borrowing causes to be subtracted from the adjacent column to the left, which is then added back as 102 to the original column.

To see how subtraction proceeds in base 2, we begin with the example of subtracting 112 from 1012 to get 102 (510 - 310 = 210):

Starting with the ones column, we subtract 1 from 1 to obtain 0. In the twos column, 0 is smaller than 1, so we must borrow from the fours column. In essence, we borrow one from the fours column to add two to the twos column. 2 - 1 = 1, which is the result in the middle column. The high-order column is left with a 0.

As another example of borrowing, consider the subtraction of 1112 from 100012 to yield 10102. To see borrowing in the longhand form, let's look at the step-by-step process:

Steps (i) through (v) show the transformations to the positional notation to get a form suitable for subtraction of 1112. (i) is 100012 in the standard form. Since the twos position is smaller than the digit being subtracted from it, we must borrow from the fours position. This is shown in (ii). Now the fours column is negative, so the borrowing process must cascade. The result is shown in (iii). Now the eights column is negative, so the process continues, as (iv) shows. The final form, suitable for subtraction, is shown in (v). Now we can perform the subtraction column by column to obtain the final result of 10102.

In general, the strategy for subtraction is summarized by

Using this table, let's subtract 100002 from 10111112 (9510 - 1610):

In this example, there is no need to borrow. You should verify that 10011112 = 7910.

As a final example, let's consider the subtraction of 1 from 100002 to yield 11112:

This example exhibits cascaded borrows. We begin with the rightmost column. 0 is smaller than 1, so the result is 1 with a borrow of 1 from the column to the left.

Let's look at the second column. It has a deficit of 1, because it has lent a 1 to the column to its right. This is equivalent to subtracting 1 from this column. We must borrow from the next column to the left to make good on this deficit. Thus the column computation is the same as 102 - 1 = 1 with another borrow from the left.

The process repeats for the third column. The deficit of 1 used as the borrow into the second column must be made good. Since the current column has 0 in it, we must borrow from the fourth column. After the borrow, the calculation becomes 102 - 1 = 1 with yet another borrow from the left.

The reasoning for the fourth column is the same as for the third. The borrow comes from the fifth column to make good on the deficit for the fourth column. 102 - 1 = 1. In the fifth column, the calculation becomes 1 - 1, based on the borrow deficit. The final result is 011112.

[Top] [Next] [Prev]

This file last updated on 07/16/96 at 05:10:10.
randy@cs.Berkeley.edu;


What is Sarbanes-Oxley[q]
What is Sarbanes-Oxley[q]
ISBN: 71437967
EAN: N/A
Year: 2006
Pages: 101

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net