Computer Concepts FAQs

Course Content

A.: The simplest way is to download a binary-decimal converter calculator from a shareware site. CalcWorks is such a calculator for the Mac. That, however, does not help you to understand the basic concept. I trust the following discussion will cover that area.

Consider decimal numbers first.

Numbers have place value in the decimal system just as they do in the binary system.

In the decimal number 47, the 7 is in the units place and the 4 is in the tens place.

This is another way of saying, the 7 is multiplied by 1 and the 4 is multiplied by 10

this is another way of saying the 7 is multiplied by 10^0 (ten to the zero power) and 4 is multiplied by 10^1 (ten to the 1st power)

in a number like 1023, you have 4 numbers each with a separate place value. Place value begins with the far right number and takes the base (in decimal the base is 10, in binary the base is 2) to the zero power (anything to the zero power is one). So we call the place value "units" in decimal. As it happens, it is units for any base as the value of any base to the zero power is "one".

Now in our number 1023, 3 is times 10^0, 2 is times 10^1, 0 is times 10^2, and 1 is times 10^3. The powers of ten rise (increment) by one as the places move one by one from the far right to the left. Zero, then 1st, 2nd, 3rd, 4th, etc.

this model shows it better than words:

We can form a simple math problem with the number 1023:

(1 x 10^3) + (0 x 10^2) + (2 x 10^1) + (3 x 10^0) =

(1000) + (0) + (20) + (3) = 1023

Let's convert binary into decimal

We have to follow a similar procedure in the binary system when the base is two. For example if we had a binary number 101010, what would the decimal equivalent be? Well, we have only 2 numbers in binary, 0 and 1. But we have infinite possible place values.

876543210	<-- powers of the base
101010	<-- our "number"

In this case we raise the base, 2, to the power shown above the number

(1 x 2^5) + (0 x 2^4) + (1 x 2^3) + (0 x 2^2) + (1 x 2^1) + (0 x 2^0) = ?

now what are the powers of 2

0 <--- zero the "place holder" representing nothing or a void
2^0 = 1 <-- 2 raised to the zero power
2^1 = 2
2^2 = 4
2^3 = 8
2^4 = 16
2^5 = 32
2^6 = 64
2^7 = 128
2^8 = 256
2^9 = 512
2^10 = 1024 <-- remember 1K ? this is why it is not exactly 1000. It is actually 2^10.

So we can now solve the math problem and convert binary into decimal by substituting the decimal equivalent for the power of 2 in the problem just above.

(1 x 32) + (0 x 16) + (1 x 8) + (0 x 4) + (1 x 2) + (0 x 1) =

32 + 8 + 2 = 42


To reverse the process (convert decimals to binary numbers) we need to compare our decimal number to the powers of 2 table (shown above).

Find the largest power of 2 less than or equal to the decimal number. Put a "1" in the place value position for that power of 2; subtract that amount from the original number. Take the remainder and repeat the process until the remainder is zero. Any remaining powers of two to the right of the initial "1" become place holders or zero. (Yes, we need to make sure that our 1's stay in the correct places.)

So let's take Module 6.5, problem 2.b. Convert the decimal number 358 to binary.

First set up our place value model

876543210	<-- powers of the base "2"
	<-- our "number"

Keep in mind the 2 "times table" shown earlier.

In the times table, bracket the number 358 (find the power of two immediately higher and lower. The number lies between 256 and 512 so it is between 2^8 and 2^9. So 2^8 is the largest power of two that is less than or equal to our original number 358. So we put a "1" in the place value 2^8.

876543210	<-- powers of the base "2"
1	<-- our "number"

We then subtract 2^8 from out original number. 358 - 256 = 102.

We now repeat the process with the remainder until the remainder is zero. If there are any places to the right of our first "1" not yet filled in, put a zero in those places (we merely make sure no one mistakes the place value of the numbers we have already assigned to specific places. You might want to enter intermediate place holders as you go along just to keep yourself straight.

Now, work through the number. You should get 101100110

Notice also that there are nine digits, just as there are nine places with possible values in the model above - one more than the power to which we raise the base because our first power, on the far right, was zero.

Hope this helps.

 

A.: Use the Module 6 PIPPIN assembly language generator to get you started.

You need to recognize and implement all three phases - scanning, parsing, and code generation.

In Module 6.5 Exercise 16, for example, we are asked to describe the process of getting from a programming statement to code generation.

Scanning:

Normally we could start with parsing immediately from a formula. However Exer. 16.1 is not in a form recognized by PIPPIN - the token "+=" is not recognized even though it is a valid JavaScript operator. So we must recall the meaning of "+=" assignment operater in JavaScript.

In words, we take the plus "+" first. This represents adding the value on the left of the operator to the value on the right. The equal sign "=" portion of the operator is the typical assignment operator - take the portion on the right of the operator (now increased by the value on the left) and assign it to the value on the left.

(See also information on JavaScript operator += , "Add by value".)

For example, "x += y" would read in algebra "x = x + y"

So, in Exercise 16.a) of Module 6.5, convert the statement

x += 1

to a more familiar, algebraic equation

x = x + 1. This completes the scanning phase for the PIPPIN code generator (and we) can now parse this equation

Parsing:

Your parsing tree will look something like this.

The upper version more correctly shows the recursive nature of the statement. The alternate version is perhaps more familiar. You need to solve the right branch and then assign that value to the left branch - the initial value of x in the right branch equals the initial value of x in the left branch.

Code Generation:

So, now all we need to do is implement the parsing tree in PIPPIN Assembler

Based on using the Accumulator we would see the value at address X and load it into the Accumulator, add the value 1 and then store the result in address X. The PIPPIN assember code would be

LOD X
ADD #1
STO X

 

In exercise 16.b) the problem is more complex.

We are given the JavaScript statement

if (X == 2) X=0

In words, if the value at location X equals "2", put "0" in location X.

Again, in order to generate the code, we must first scan, then parse and finally generate the code.

When we scan, we find that all tokens are recognized by the PIPPIN Assembler except the conditional "if", the association operators "()", and the equality symbol "==".

We can construct a parse tree with an 'if' statement. We need to refine the tree to get it into tokens our assembler will recognize but we will leave that for later.

For now, let us look at generating code that will synthesize the "if" statement (see the PIPPIN User's Guide, page 211). We take care of the association operators "(" and ")" by doing this comparison first. We take care of the comparison by matching the value in the accumultor to zero as follows:

LOD X
SUB #2
JMZ 5
JMP 6
STO X
HLT

Note that I check for X equals 2 by checking for (x-2) = 0. This allows me to use JMZ (jump on zero) to move the program to line 5 and to merely store the value of the accumulator, now zero, in location X prior to halting the program. If the accumulator is not zero, I halt the program immediately leaving the value at location X unchanged. At this point, if X was not equal to 2 at the start, I do not know the value in the accumulator other than it is (X-2).

Hope that helps.

 

A.: Curly braces { ... } mark off a block of statements that are to be taken together.

Statements outside the braces are not part of the block, those inside are part of the block.

Within the block, firing sequence is determined by control statements or the incremental flow of statement (one up throughout the program is the imputed order).

The use of curly braces in control statements shows that all of the statements within the braces are part of the control statement and conditions.

Revised 3 March 2000

Phil Richardson; prichard@faculty.ed.umuc.edu