Computer Science 161.01

Professor Valente

Wednesday September 4^th

READING: Chapter 2 but limited to whole numbers.

It’s All a Matter of Interpretation

Suppose I tell you that the computer currently has a particular 8-bit pattern, say 10101001, in a certain memory location.

How do we know what this represents?

It might be part of the 24 bits needed to represent a color. In other words, 10101001 could mean that the amount of Red is xA9.

It might be an instruction in the VSC-32’s machine language (ADD what’s at memory location 9… more about that when we study the VSC-32).

It might be that the last 7 bits 0101001 indicate the closed-parenthesis character, according to the ASCII code.

It might be the integer 169 (as we’ll learn shortly), if we agree to interpret the pattern as a non-negative integer.

Or it might be some negative integer, if we agree to allow that as part of the interpretation.

Or it might be some floating point (i.e. fractional) number if that’s what we have in mind for it.

Many students are troubled by all of this uncertainty.

The good news is that you don’t need to be.

It’s the hardware’s responsibility simply to maintain the bits 0 and 1 in all the appropriate places.

But the software (a program) will then interpret the bits in whatever way it chooses.

(You saw the differences early on when we treated 23 first as a number, then as a string).

Interpreting a bit pattern as a non-negative integer (binary to decimal conversion)

If I ask you to interpret some 8-bit pattern as a non-negative integer, what is the range of values you might get?

Well, there are 2⁸ such patterns, so the range of values is 0 thru 255, since we’re not involving negative numbers.

So, if I ask you to interpret the 8-bit pattern 10101001 as a non-negative integer,

you’ll know you’d better get an answer in the range 0 thru 255.

There are two methods you can use to get the answer.

Binary to Decimal: Method 1:

Expand the 8-4-2-1 method from 4 bits to 8-bits.

What “coin values” do we have if we do this?

Notice the coin values double from right to left, so continue this!

Our values are now 128-64-32-16-8-4-2-1.

So the pattern 1 0 1 0 1 0 0 1

Represents 128 + 32 + 8 + 1, which is 169. Hooray!

Binary to Decimal: Method 2: Imagine that you can see the bits (or are told the bits) one at a time, left to right.

With this method, you’ll just keep track of a total that will grow in the end to 169.

Here’s how it works:

Begin with total = 0. Start at the left.

For each bit that you see, do the following

If the bit is a 0, double the total.

Else if the bit is a 1, double the total and add 1.

Move right to the next bit.

After you’ve seen all the bits, report the total.

Let’s try Method 2 now!

Underneath each bit in 10101001, I will show the running total as I step through the above algorithm.

Bit 1 0 1 0 1 0 0 1

Total 0 1 2 5 10 21 42 84 169

--------------------------------------- >

With each bit, I double or double-and-add-1…

Another example: Convert 00011010 to a non-negative integer.

Bit 0 0 0 1 1 0 1 0

Total 0 0 0 0 1 3 6 13 26

--------------------------------------- >

With each bit, I double or double-and-add-1…

Practice this using this site I developed, making sure that unsigned is selected and

that you enter Binary and press the Binary - - > To Decimal button.

While you are doing this, try to determine a way to start with the decimal integer and convert it to binary!

We’ll do this next.

Now, let’s suppose we were given only 169 and asked to represent that as an unsigned 8-bit integer.

We know we’re supposed to get 10101001, but how would we get that??

We really want to invert what we did above.

So we’ll start with 169, move right to left, and record the appropriate bit above.

Let’s look again at what I did in the previous two examples, but reverse the arrows.

Bit 1 0 1 0 1 0 0 1

Total 1 2 5 10 21 42 84 169

<-------------------------------

Bit 0 0 0 1 1 0 1 0

Total 0 0 0 1 3 6 13 26

<-------------------------------

In the first example, what is it about 169 that caused a 1 to be above it?

In the second example, what is it about 26 that caused a 0 to be above it?

If you answered that 169 is odd, and 26 is even, you got it!

You know that I can’t give you 169 cents without including 1 penny!

And I can’t give you 26 cents with 1 penny!

Now, I’ll list 84 to the left of 169, and 13 to the left of 26. Why??

What did I do arithmetically when I moved left in each case?

I “halved” the number (throwing away any fractional part).

See if this pattern continues throughout as you move right-to-left in both of these examples.

Let me now list the algorithm I have suggested:

Decimal To Binary:

Start at right end and write down the decimal number you have as input.

If the number you wrote is odd, record a 1 above it, otherwise record a 0 above it.

Do the following 7 times (assuming you want 8 bits):

Move left and “halve” the decimal number.

If the number is odd, record a 1 above it, otherwise record a 0 above it.

Note: When you use this algorithm with a positive number to begin with, the number will become 1

at some point, and that will correspond to the leftmost 1 you record in the bit pattern.

Of course “halving” 1 leaves you with 0, so you will have 0 from then on.

It is strongly recommended that you practice with this site again but still with unsigned selected at top.

(This time, of course, you will be entering a decimal number on the right and clicking the button on the right).

In this final algorithm, I chose to focus on an algorithm that did in reverse what Method 2 did.

Of course there is a Decimal-To-Binary method that will record the bits properly just as well, and that reminds us of Method 1.

Think of owing someone 169 cents, and how you will give them change.

Remember that you have exactly 1 each of 128, 64, 32, 16, 8, 4, 2, 1.

Well, you’d better give the person a 128-cent piece (Yes to 128).

Now you owe 41 cents.

Will you give a 64? No way! (No to 64).

How ‘bout 32? Yes… then you owe 9… and so on.

169 = 1 0 1 0 1 0 0 1

Yes No Yes No Yes No No Yes

128 64 32 16 8 4 2 1

---------------------------------------- >

More simply put, 169 is 128 + 32 + 8 + 1, so say Yes(1) to those values and No(0) to the others.

Important Message From Professor: Do not be overwhelmed. What you have seen are two methods for converting 8-bit patterns to

unsigned decimal integers, and 2 methods for converting decimal integers to 8-bit unsigned integers.

You may choose one of each!

On to Friday's Notes