What kind of data can we process with TOY.

Well we've talked before that all data and computers encoded in binary.

So, it's a matter of the encoding we can process any data

in TOY but let's look specifically at what we're talking about.

So, the concept of a data type that we

started within Java programming definitely applies here.

A data type is a set of values and a set of operations on those values.

So, that's what we need to talk about to describe how TOY operates.

TOY's data type is called 16 bit two's complement integers.

You know what 16 bit means and we'll talk about

two's compliment in just the next couple of slides.

And there's two kinds of operations that it can perform

on these 16 bit two's complement integers.

One is arithmetic, you can add

the integers and in

your computer you can multiply and divide them and other things like that.

Arithmetic operations, every computers got a full suite of arithmetic operations.

And the other kinds of operations are bitwise operations where we treat

the integers as sequences of bits and we perform bit by bit operations.

We saw that in our cryptography example at the beginning of the course,

where we did bitwise exclusive or

operations in order to implement a cryptographic protocol.

It turns out that there's lots of operations that we perform in

computer and data processing that require

this type of operation so they're built into all computer hardware.

But every other type of data and

every other operation has to be implemented with software.

If you want to have 32 bit integers you're going to have to write code

that takes two 16 bit integers and treats them as 32 bit integers.

If you want floating point values you have to come up

with an encoding and write software to do this.

If you want characters and strings again,

you're going to have to write programs that take the built

in data type and then treats them as characters and strings,

and so forth and so on.

And what we're doing here is reflecting

what life was like when the first computers were built.

And really all there were were these kinds of operations.

And all of these other things were implemented in software.

Eventually many of them found their way to hardware so that

their basic operations were encoded in hardware on your machine.

But still it's important to remember that that dividing line is not so absolute.

And really we're just implementing abstractions,

sets of values and operations on those values.

Sometimes we do it in hardware,

sometimes we do it in software and at the level that we usually

program we don't know the difference except for performance.

So, for TOY all values are represented as

16 bit words and that's what we're going to be mainly talking about.

And the way that we communicate then is with switches and

lights and we'll see that in great detail in just a minute.

So, the original design for TOY and this is true actually of many computers.

Let's just work with unsigned integers values from zero,

two^16 minus one encoded in binary and then we talk about them in hex.

So if we want the number 6,375 in

decimal then we can look at the binary encoding of that thing,

this is it adds two to the 12th plus to the 11th

plus 2726 to the fifth to the second 222120.

That's a binary representation of 6,375.

We can convert it to hex by taking four bits at a time.

And this is just just a little check if you don't believe our binary to hex trick

that's one time 16 cube plus eight times 16 square

plus 14 times 16 plus seven, same number 6,375.

And then we can perform operations on these numbers like add and

subtract or test if it's zero just as we would with binary numbers.

So if we want to compute double of 18E7 or 6,375 then we just add

the binary numbers and adding binary numbers

is just using the grade school algorithm of add the two digits and

carry and in this case that's the result that you get

and you can convert that one digit at a time to get 31CE.

And I will ignore overflow,

it's a detail that we can do in an exercise but that's the original design of TOY.

The things that you could do.

So what happened with TOY and actually what happened with lots of real computers

is that people realized that without really any work,

it's possible to change the data type and allow

us to process negative integers really without changing the computer at all.

So it's interesting to see why this works and it's

worthwhile knowing about it because every computer

uses two's complement to represent

integers for the purpose of also including negative integers.

Can support the same operations easily add,

subtract, test of positive, negative or zero.

And the rule is simple if we have a positive number,

we just use the 16 bit representation of X.

If we have a negative number,

we use the 16 bit representation of two to the 16th minus the absolute value of X.

Now we can only go from minus two to the 15th to two to the 15th minus one.

That is we can only encode half as

many positive integers because we want to encode the negative integers as well.

So in 16 bits the biggest number that

we can represent is two to the 15 minus one which is 32,767.

So in hex that's 7FFF,

which is a zero followed by all ones,

that's the biggest positive number.

And then if we subtract one then we get

smaller and smaller ones until we get eventually down to three, two, one.

This is the standard binary representation of positive numbers and zero.

But as soon as we go negative,

if we want to do negative one the representation of that is

two to the 16th minus one which is all ones or all F's and hex.

And then those numbers we keep discriminating by one

and eventually we get to the smallest negative number that we can represent,

which is one followed by all zeros.

And it takes a few minutes to get used to this representation.

Now I'll just describe its properties that there's one thing that's slightly

annoying is that we have one more extra negative value than positive value.

So we can represent minus two to the 15th but we can't represent positive two to

the 15th and the reason for that is that there's just one representation of zero.

But this representation has useful properties.

So, one of them is the leading bit always signifies the sign.

If the leading bit is zero then it's a positive,

if the leading bits' one, then it's negative.

There's one representation of zero and that's when all the bits are zero.

You might say, "Why not just use the first bit for the sign?"

But then if you do that, then you have

two different zeros and that makes things complicated.

But the other thing that's interesting is that you can do add and

subtract just the same as you would if they're unsigned. We'll look at that.

You don't have to change the hardware at all,

then you get to process negative numbers for free.

Besides the mathematical rule,

we want to be able to convert from decimal and in hex and in binary two's complement.

So, how do we get a decimal number into two's complement?

Well, first thing is if it's outside the range,

you say you can't do it.

So, if it's bigger than 250 minus

one or less than minus two 15th we can't fit it in a 16-bit two's complement number.

Otherwise, I take magnitude of the number and convert it to binary,

if it's zero or positive then you're done, that's all it is.

And if it's negative, what you do is flip all the bits and add one.

An easy operation.

So let's look at an example.

So for example, the number 13 in decimal is all zeros 1101.

Eight plus four plus one is 13,

or in hex it's 000D.

To get the representation of minus 13,

you just flip all the bits,

which is all ones 0010 and then add one,

and we get all ones 0011.

Or in hex's FFF3.

Very easy operation to convert from decimal,

first you convert to binary for the magnitude,

and then if it's a negative flip all the bits and add one.

To go the other way to convert from two's complement to decimal,

now you do the opposite.

If the sine bit is one that means it's negative,

so you flip all the bits add one and then I'll

put the minus sign just convert to decimal.

So for example, if you have the hex number 0001 that's all zeros and a one,

you want to know the binary representation of minus one,

you flip all the bits that's all ones and a zero,

add one you get all ones that's a representation of minus one.

And there's the example for 243.

Flip all the bits and add one since minus two

for three starts with the one if you want to get

positive you flip all the bits and add one.

So very simple conversion from a negative number to a positive number.

And then again, just to add and subtract and just have to do an example to start

to believe this in the book if you read it more carefully we do the math that proves it,

but if you take minus 256 there's that example and plus 13.

And forget about the representation just treat them as positive 16-bit integers,

you get the right answer for two's complement.

So people realized they had built machines that just work with

positive integers but with two's complement

they also work with negative energies as well.

There's just one problem and that's overflow,

and we're ignoring overflow,

but still it's one that you want to know

about because every beginner programmer runs into it right away.

And we ran into it right away with the first couple of Java programs.

So if you have the largest positive number say in 16-bit

says two of the 15 minus one that's a zero followed by all ones.

Now, this is the one case that addition doesn't work if you add one to that,

then we're adding all zeros and a one to it.

So the one plus one is zero carry one carries

go all the way over and the result is one followed by

all zeros are in hex 8000 and that's the representation of the smallest negative number.

If you're not checking for overflow and you just incrementing,

you find that your largest positive number

all of a sudden becomes the smallest negative number.

And many beginning programmers see that in their early programs numbers get too big,

all of a sudden they become negative,

so this is the reason.

It's well catalogued, you can find many examples.

And this is an xkcd on somebody's counting sheep and overflowing and then well,

that's the computer scientists joke of the day.

Okay. So that's the arithmetic operations.

What about bitwise operations?

TOYs got a bunch of bitwise operations

and they're familiar operations that we've seen in other contexts.

Actually in Java you can do this same operations although we haven't used them much.

So the idea is just for each bit position implement the basic Boolean Function.

So the end function is,

if x and y are both one, otherwise it's zero.

And again we've seen this function in other contexts but what

this does is it does it for every bit in the 16-bit world.

So the first two are zero and zero,

then 100, and then two zeros and it's zero.

And then, we have a couple where they're both one so the result is one and so forth.

So that's the Bitwise AND operation.

And actually, we use that for isolating some bits in a word.

So for example in this case,

the first three bits are zero but then there's a bunch of ones in a row.

And if you look at it, the result of

ending against those ones just gives the bits and the other work.

So if you wanted to isolate those bits,

you could use an AND operation with a mask of ones in this way.

And we'll do this later on.

And then there's bitwise XOR.

Again XOR is the one that we use for

our krypto example that function is zero if the two bits are the same,

and one if the two bits are different.

So in this case again it does it for each one of the bits.

So the leftmost there are both zero so it's zero,

then for a while then the next one is,

one of them's one so it's one and then they're both zero and they're both one,

so those results are zero and so forth.

So bitwise exclusive OR is implemented in TOY hardware.

And then there's the shift operations.

So, those we just take the bits in the word and

move them a specified distance in places that are.

So, this is a shift left three,

so we move every bit to the left three positions and that leaves

us with three bits so we have to fill in and we fill with zeros.

And then their shift right which again fill with zeroes now from the right.

So shift left and shift right those are

bitwise operations that we can implement in TOY instructions.

And a special note is that the shift left and right are implement,

multiply and divide by powers of two.

And they're the basis for actually integer multiply as well.

There's one extra thing that you have to do if the leading bit is

one shift right has to fill with

the ones so that's like if it's a negative number it keeps it negative.

And that's a detail,

but it's kind of a mix of the data type are

these things bitwise operations or are they arithmetic operations.

Well for shifts there are kind of both.

And that's it, that's the summary of the operations

that are involved in the TOY data type,

those are the things that we can do on

the data values that we can represent not too much.

And It's kind of surprising that we can build up

a full computational infrastructure like

the one we've been using with just such basic operations.

But that's really the reality of today's computers.

Data Types

Computer Science: Algorithms, Theory, and Machines

Meet the Instructors