CS30 Lecture 1

How high can you count on your fingers?

10?

I can count to 1023.

This is because the representation you learn as a child is very inefficient.

Ten show the two different ways of saying the number 2.

Then show the number 505. How much is the right-most 5 worth?

5

How much is the left-most 5 worth?

500

Why are they worth different amounts?

Because they are in different positions.

So – the key is that even if you see the same number, if you give the different digits different values, you have different numbers.

For decimal numbers, we have 10 choices of what to put in each digit. That makes the first digit the 1’s, the next the 10’s, then the 100’s, etc. What is the equation that specifies the value of the nth bit from the right? 10^n.

Okay, for our fingers (and for binary), we have two position – up or down. So that means that each position must be worth twice as much as the one to the right of it. The value of the nth bit from the right is? 2^n.

Computers use binary because of the physical storage. When computers started out, they used vacuum tubes that were on or off. Now, values are stored on hard drives magnetically to have a positive or negative charge, DRAM stores values in a capacitor that is either charged up or drained, and chips store values that flow electricity to 5V or ground. All of these physical devices store only two choices of values in each space. If we had some physical structure that could be easily read that stored more values in the same amount of space, then we could have a computer that operates on other bases. But this is why everything is in binary.

Okay, so let’s look at some 5 digit numbers. Draw on the board the values 16, 8, 4, 2, 1

Let’s try translating a few numbers from binary to decimal.

01000

00010

10000

Now harder ones:

01001

00110

01111

Now look at this sequence

11000

01100

00110

00011

What is the relationship between the values you calculated?

What do you notice about the pattern in the bits?

What about these numbers in decimal? Each one divides by 10.

50000

05000

00500

00050

00005

The above sequence divided by 2. So, just as taking off a 0 on the right makes a decimal number divide by 10, taking off a zero on the right of a binary number divides it by 2.

What happens when you add a 0 to the right side of a binary number? Multiply by 2.

Okay, what is this number?

01001101001010111010000100101101

I don’t even want to try to calculate that. It’s annoying, though, because there are often numbers this long in binary. In fact, this is the number of bits that a traditional integer has on a 32-bit machine – 32 bits.

What we would like are some representations that are easier to deal with but are also very easy to translate between them and binary. Decimal is not a good choice.

Octal – base 8

Hexadecimal – base 16

The reason these translate easily is because their bases are powers of 2.

Octal – 8 = 2^3

Hexadecimal – 16 – 2^4

This means that for each octal digital, three binary digits are required to translate. For hexadecimal, you divide the binary number into sets of 4 digits and translate them.

The above number:

0b01001101001010111010000100101101

0o11512720455

0x4d2ba12d

Let’s try some short translations:

0b10010110

0o226

0x96

0o346

0b011100110

0x0e6

0x154

0b000101010100

0o0524

Okay, if I have a number

01101001

What is that number times 2?

011010010

What is the original number divided by 2?

00110100

Was the original number even or odd?

odd because the lowest digit was a 1

So what happens to division when we divide an odd number?

It rounds down.

Let’s see if we can apply this to our knowledge of high level languages.

What happens when we divide an odd integer by 2?

Let’s imagine we can store only positive integers in a number. A short integer is 16 bits long. What is the largest unsigned value that can be stored in 16 bits?

2^17-1

In languages that allow you to operate on unsigned integers, this is the limit.

Now that we have seen how to represent numbers, let’s see how to perform arithmetic.

Try adding a decimal number first:

6192

1257

Then try a binary number

1011

0110

Show how the carries work

Now try multiplication

Base 10:

1010

0101

Binary:

1010

0101

Almost the same! Note that for binary, each time you add, you add only one of two things – 0 or the second number. This makes the implementation quite simple, actually.

Now, how do we perform subtraction?

We negate the second number and perform addition

(why make new logic if we can do negation easily)

Okay, then how do we negate the number?

Ummmmm.

We haven’t shown how to represent negative numbers yet.

The first representation is very human-friendly but does not lead to a good implementation for addition. Remember – when we add -1 + 5, we want the result to be 4 hopefully using the same addition operation as we already invented for positive numbers.

Sign-magnitude representation – reserve the top-most bit to be the sign.

0 means positive, 1 means negative.

Let’s try representing -1 + 4

-1: 10000001

4: 00000100

If we add those two we get:

10000101

That is -5. Hmm. That’s not what we wanted. So even though it’s easy for us to read the binary number in sign-magnitude, it is not conducive to simple hardware implementation.

One’s Complement

The negative number is the same as positive number, but you flip all of the bits

7: 00000111

-7: 11111000

-1: 11111110

4: 00000100

Add those two and get:

00000010

-

Well, that’s closer to what we want, but not exact.

It’s off by one.

Thus, they invented:

Two’s Complement – the most widely used representation

Two negate any number (whether it is positive or negative to start out), flip all of the bits and add 1.

7: 00000111

-7: 11111001

-1: 11111111

4: 00000100

Add them up:

00000011

Hey, that’s 3! Yippee!!!!!

The subtraction logic then becomes very simple – flip all the bits of the second number, put in an adder, and add 1. Because of a clever adder design, the adding 1 can be done at the same time, with virtually no additional cost, as the main addition.