Wednesday, May 6, 2009

number systems

NUMBER SYSTEMS
Since childhood, we have learned to do our computations using the numbers 0 - 9, the digits of the decimal number system. In fact, we are so accustomed to working with decimal numbers that we hardly think about their use. We balance our checkbooks, pay monthly bills, and even solve algebra homework with the aid of the decimal number system. Considering the widespread use of this system, why should anyone bother to study the binary number system? The answer is found in something that is almost as widespread as decimal numbers: computers.
While it is fine for us to use ten digits for our computations, computers do not have this luxury. Every computer processor is made of millions of tiny switches that can be turned off or on. Since these switches only have two states, it makes sense for a computer to perform its computations with a number system that only has two digits: the binary number system. These digits (0 and 1) are called bits and correspond to the off/on positions of the switches in the computer processor. With only these two digits, a computer can perform all the arithmetic that we can with ten digits.
Our study of the binary system will help us gain a better understanding of how computers perform computations. In a way, we can think of this study as learning another language, the language of the computer. Every instruction that a computer executes is coded in this binary language. The goal of our study is to become fluent in the language of the computer by learning the following skills:
• converting between binary and decimal,
• Performing binary arithmetic,
• Representing signed binary numbers, and
• performing binary arithmetic with signed numbers.

The base of any number system is determined by the number of digits in the system. For example, we know that binary is a base-2 number system since it uses two digits and decimal is a base-10 system since it uses ten digits. Throughout our lessons, we will distinguish between various number systems by putting a small subscript after the number to indicate the base. For example, a typical decimal number would be written like 462.1510 and a typical binary number would be written like 110.112.
In order to convert between binary and decimal numbers, we need to understand the relationship between the digits of a given number, the position of those digits, and the base of the number system. Let's take another look at our example number in the decimal system.
Hundreds Tens Ones Tenths Hundredths
102 101 100 10-1 10-2
4 6 2 . 1 5
The first digit of our number is 4, but because this digit is located in the hundreds column, we know it really represents the value 4 * 102 or 400. Similarly, the 6 in the tens column represents the value 6 * 101 or 60. Continuing this pattern, we can express the number 462.1510 as follows:

4*102 = 4*100 = 400.
6*101 = 6*10 = 60.
2*100 = 2*1 = 2.
1*10-1 = 1*.1 = 0.1
5*10-2 = 5*.01 = + 0.05
462.15
In general, the relationship between a digit, its position, and the base of the number system is expressed by the following formula:
DIGIT * BASE POSITION #

CONVERTING BINARIES TO DECIMAL

1. First we write the binary position values above each digit. Note that 2 raised to the 0 power is located to the immediate left of the radix point. As we move to the left, the power of the position is increases by 1 for each digit. And as we move to the right the power of the position value decreases by 1 for each digit.
2. Next, we convert these position values to their decimal equivalents. For each column, we multiply the position value of the column by the digit contained in that column. Since any number multiplied by zero equals zero, we ignore the columns with digit “0”. The remaining columns all contain “1”s so we can simply record their position values below.
3. Finally, sum the values we listed to get the decimal answer.

CONVERTING DECIMAL TO BINARIES

In order to convert a decimal number to its binary equivalent, we will repeatedly divide the decimal number by 2, the base of the binary system. Division by 2 will either give a remainder of 1 (dividing an odd number) or no remainder (dividing an even number). Collecting the remainders from our repeated divisions will give us the binary answer.

When converting a fractional decimal value to binary, we need to use a slightly different approach. Instead of dividing by 2, we repeatedly multiply the decimal fraction by 2. If the result is greater than or equal to 1, we add a 1 to our answer. If the result is less than 1, we add a 0 to our answer.

BINARY ARITHMETIC OPERATIONS
Now that we understand how to convert between binary and decimal numbers, we are going to learn how to perform addition, subtraction, multiplication, and division with binary numbers. For each of these operations, the technique used to solve the binary problem will parallel the technique you learned to solve decimal problems. When you work through the example problems, you can verify that your binary answers are correct by converting them back to decimal.
As you work through these lessons, it is important to note that multiplication and division are really just repeated addition and repeated subtraction. When we do a multiplication problem like 5 * 3, we are really just computing the sum of 5 + 5 + 5 which is a repeated addition problem. When we do a division problem like 15 / 5, we are really just computing the number of times that 5 can be subtracted from 15. We will return to this idea a little later since it affects the way that computer processors perform binary arithmetic.
ADDITION

We need to learn four basic rules in order to perform binary addition. These rules are listed in the table below. Notice that the first three rules are quite simple since there is no difference between these binary rules and the corresponding decimal rules. The fourth rule, however, is different from decimal. Any time that we add two 1s together in binary, we generate a carry to the next column since the binary system only has two digits. In decimal we have 10 digits, so we do not generate a carry until the sum of two digits is greater than or equal to 10 (e.g. 5 + 7 = 12).
Rule 1 Rule 2 Rule 3 Rule 4

0
+ 0
0
0
+ 1
1
1
+ 0
1
1
+ 1
10
We can use these rules to derive another important rule for binary arithmetic. Consider what happens when we try to add three 1s together in binary. Let's split the problem into two addition problems and apply our rule for binary addition to find the answer.
SUBTRACTION
To do subtraction in the decimal system we normally use the borrow method. Consider the example problem to the right. Here we must borrow a 10 from the tens column in order to complete the subtraction in the ones column. We move 10 to the ones column and subtract 6. Then we copy down the remaining 20 from the tens column to get our answer of 24. 2(10)
3 0
- 6
2 4
We can also use the borrow method to do binary subtraction. The basic rules for binary subtraction are listed in the table below.
Rule 1 Rule 2 Rule 3 Rule 4

0
- 0
0
1
- 1
0
1
- 0
1
0
- 1
1
Again we see that the first three rules are similar to their decimal counterparts. The fourth rule, however, needs a little more explanation since it defines how we borrow from another column.
MULTIPLICATION
Binary multiplication uses the same technique as decimal multiplication. In fact, binary multiplication is much easier because each digit we multiply by is either zero or one. Consider the simple problem of multiplying 1102 by 102. We can use this problem to review some terminology and illustrate the rules for binary multiplication.
1. First, we note that 1102 is our multiplicand and 102 is our multiplier. 110
x 10
2. We begin by multiplying 1102 by the rightmost digit of our multiplier which is 0. Any number times zero is zero, so we just write zeros below. 110
x 10
000
3. Now we multiply the multiplicand by the next digit of our multiplier which is 1. To perform this multiplication, we just need to copy the multiplicand and shift it one column to the left as we do in decimal multiplication. 110
x 10
000
110
4. Now we add our results together. The product of our multiplication is 11002. 110
x 10
000
110
1100
When performing binary multiplication, remember the following rules:
1. Copy the multiplicand when the multiplier digit is 1. Otherwise, write a row of zeros.
2. Shift your results one column to the left as you move to a new multiplier digit.
3. Add the results together using binary addition to find the product.
DEVISION
We can calculate binary division problems using the same technique as long division in the decimal system. It will be helpful to review some of the basic terms for division. Consider the division problem below.
In this problem, the red 6 is the divisor, the blue 33 is the dividend, the black 5 is the quotient, and the green 3 is the remainder. We will use these same terms to describe how binary division is done. 5
6|33
30
3
Now let's look at a simple division problem in binary: 112 / 102 or 310 / 210. This time 102 is the divisor and 112 is the dividend. The steps below show how to find the quotient which is 1.12.
1. First, we need to find the smallest part of our dividend that is greater than or equal to our divisor. Since our divisor has two digits, we start by checking the first two digits of the dividend.
10|11
2. 11 is greater than 10, so we write a 1 in the quotient, copy the divisor below the dividend, and subtract using the borrow method.
1
10|11
10
1
3. Since we have no more digits in our dividend, but we still have a remainder, our answer must include a fraction. To finish our problem we need to mark the radix point and append a zero to the dividend. 1.
10|11.0
10
1
4. Now we bring down the extra zero and write it beside our remainder. Then we check to see if this new number is greater than or equal to our divisor. Notice we ignore the radix point in our comparison. 1.
10|11.0
10
10
5. 10 equals the divisor 10, so we write a 1 in the quotient, copy the divisor below the dividend, and subtract. This completes our division because we have no more digits in the dividend and no remainder. 1.1
10|11.0
10
10
10
0
When doing binary division, we need to remember some important rules:
1. When the remainder is greater than or equal to the divisor, write a 1 in the quotient and subtract.
2. When the remainder is less than the divisor, write a 0 in the quotient and add another digit from the dividend.
3. If all the digits of the dividend have been considered and there is still a remainder, mark a radix point in the dividend and append a zero. Remember that some fractions do not have an exact representation in binary, so not all division problems will terminate.

No comments:

Post a Comment