0:03

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.

Â