Two thinks you look very nice today. Oh wait, it's not supposed to say "compliment." I meant to say "two's complement" (with an 'e' in the middle of that second word), as in "those shoes would complement two's outfit very well." That time I used the right word at least, but we're still not supposed to be talking about fashion.
What's really going on is that I'm finally going to talk about negative binary numbers. I kept putting this off because I think it's confusing, and I don't want anyone who reads this to feel confused (other than the confusion I intentionally created with the first paragraph). There are two things about two's complement numbers that are difficult for people (including me) to remember and understand. The first is how to convert a positive binary number into its negative, two's complement form. The second is why we would even want to do that, and what benefit comes from going to the trouble.
It's simple to represent a negative number. Just take the original number and put a '-' in front of it. Unfortunately, with binary numbers in computers we don't have minus symbols. All we have are 0s and 1s. So that means that using only 0s and 1s we somehow have to differentiate between positive and negative numbers. In the two's complement form we do this by kind of pretending that the "most significant bit" is the positive/negative symbol (if it's 0 it's a positive number, and if it's 1 it's a negative number). We call this the "sign bit."
I have to clear up something from that last sentence. The "most significant bit" is the left-most bit when writing out the binary number, and its value has the biggest effect on the final value of the entire binary number. For example, in an 8-bit number, the "128s place" bit is the most significant bit. The 1 in 0b100 0000 is the most significant bit.
So now we know to look at the most significant bit to see if we're dealing with a positive or negative number, but the trick with two's complement is what's going on with all the rest of the bits. It's not enough to put a 1 for the sign bit and then read the rest of the bits the same as we always did. Two problems with that. First, it would be too easy. Second, it makes addition and subtraction of negative numbers more complicated than I'll show it is in a minute.
With two's complement you have to do the following to turn a positive number into its negative (I've put this off until the last possible moment): First, invert all the bits (turn all the 0s to 1s and vice versa). Second, add 1 to it. I know. It doesn't make sense. It sounds stupid. Sure, maybe the first part, flipping all the bits, can be justified because negative numbers live in Bizzaro World, so maybe everything's just opposite of a positive number. But why add 1 after that? I don't have a good explanation of that, other than that the resulting representation of the negative binary number is very convenient.
Let's do a couple of examples using 8-bit binary numbers to clear our brains.
0b0000 0001 (decimal 1)
invert all the bits
0b1111 1110
and add 1
0b1111 1111
So the two's complement representation of -1 is 0b1111 1111. Note that the most significant bit, or sign bit, is 1, meaning this is a negative number.
0b0100 1111 (decimal 79)
invert all the bits
0b1011 0000
and add 1
0b1011 0001
Again, notice that the sign bit is one, so this is a negative number.
Before I tell you the big payoff we get for going to all this trouble to use two's complement, I'll tell you about the drawback, or rather the perceived drawback of doing this. If we have an 8-bit number, and we're using one of those bits to be the sign bit (in other words, that bit is tied up telling us whether the number is positive or negative, it can't tell us about the magnitude of the number any more), then we only have 7 bits left to tell us about the magnitude of the number. With 7 bits we can only represent positive numbers from 0-127, as opposed to the 0-255 we could represent with 8 bits.
So we have about half the positive numbers we had before, BUT we also have all the negative numbers, so it turns out we can represent just as many numbers with a "signed" binary number, it's just a different range of numbers than an "unsigned" binary number can represent. With a signed 8-bit number we have the positive numbers 1 to 127, the number 0, plus the negative numbers -1 to -128, for a total of 256 different numbers we can represent. It's kind of a weird thing that we can count 1 further into the negative numbers than we can count into the positive numbers when using a signed binary number. That's one of those weird things you just have to remember.
Okay, now we'll finally talk about the payoff. That multi-bit adder we designed many articles ago can be used, no problems, no modifications necessary, on signed two's complement numbers. That's it. That same adder we designed to add positive, unsigned-only, binary numbers can be used to add signed, two's complement numbers also, AND IT TREATS THEM CORRECTLY AS NEGATIVE NUMBERS. Holy crap, it's like magic. Seriously, when I first learned this I was like "yeah, but, there's no way that actually is true." Except it is.
In fact, it's so magical that we can just design one adder, and then we can use it to add any combination of positive or negative numbers together. We can add two positive numbers, two negative numbers, or one of each. Subtraction also becomes very easy. You just convert the number you want to subtract into a negative number (using the exact same process we did above), and then add it to the number you want to subtract from. BAM! Subtraction.
This article has already grown far too long, so I'm going to hold off on doing examples of subtraction until my next entry.
Monday, March 21, 2011
Wednesday, March 16, 2011
Our current picture
We've covered a lot of ground, shared a few laughs, and now I want to review where we are now and how we got here before we move on to the next topic.
First we talked about single bits, how they are "things" (whatever that means) that are always in one of two states (on/off, up/down, 0/1, black/white, whatever). Bytes are series of 8 bits, and can be used to represent binary numbers. Binary numbers use base two (instead of base ten in decimal), so all of their digits are either 0 or 1, and these digits can very conveniently be represented by individual bits.
Once we had some understanding of binary numbers we moved on to performing math on those numbers. First we talked about the single-bit adder, and then how we can perform multi-bit addition using a series of single-bit carry adders.
Next we talked about computer memory. Computer memory is like a big long ordered list of numbers. Each number in the list has an address associated with its place in the giant list, so if you know a memory address you can look to see what number lives there. Loading means to read a number from the memory and storing means to put a number into the memory (destroying forever what was in that memory location before).
We also talked about what kinds of information those numbers in the memory can represent. They can be either instructions or data. Data can have any meaning given to it by the person programming the computer. For example a programmer could interpret a binary number in the memory as a few things: the number itself, a specific color, a location on a map, a kind of food, or anything really. It just depends on what the programmer wants for the data to stand for. It's up to the programmer to be consistent with how he treats the data, because the computer itself doesn't care about that at all.
Instructions are the other kind of information that can be stored in memory. Instructions tell the computer's processor what to do next. There's a special register in the processor called the program counter (PC) that tells the processor where, in the memory, its next instruction will come for. The processor fetches (or loads, in memory terms) that instructions, figures out what it says to do, and then does it. After this it moves on tot he next instruction (by increasing the PC) and repeats the process.
Or does it? We also learned about special processor instructions called jumps and branches which directly change the value of the program counter. Jumps unconditionally change the value of the PC to whatever the programmer wants. Branches might change the value of the PC, depending on some condition, like if one variable's value is greater than another variable's value. Once we knew about branching and jumping we could write just about any computer program under the sun, and we looked at an example that shows how we can create a loop using branches and jumps that adds a number to itself several times, essentially performing multiplication.
The last thing we talked about is the register file of the processor. Each processor has a number of registers that are temporary storage for whatever's in the memory, and act as the variables in all of the instructions the processor can execute. The registers don't have addresses the say way that memory locations do, but they still do have distinct names, like $r0 and $r17. Long, complicated programs consist of many loads from memory into registers, additions, branches based on the contents of registers, jumps, and stores back into memory. Even the most complicated programs can be broken down into these elemental pieces.
The last thing we talked about is one other operation that we can perform on registers, and that is the shift. Shifting can be done in either the right or left direction, and these operations are mathematically similar to division and multiplication. The catch is that a single shift operation can only multiply or divide by powers of two. If you want to multiply by numbers other than powers of two, then you need to get more creative. We'll talk about these ways at some future time.
And now we're here. If you missed any posts go back and start from the beginning. I'm trying to build on all of my previous posts, hopefully forming over time one big picture of computer science that anyone can understand.
First we talked about single bits, how they are "things" (whatever that means) that are always in one of two states (on/off, up/down, 0/1, black/white, whatever). Bytes are series of 8 bits, and can be used to represent binary numbers. Binary numbers use base two (instead of base ten in decimal), so all of their digits are either 0 or 1, and these digits can very conveniently be represented by individual bits.
Once we had some understanding of binary numbers we moved on to performing math on those numbers. First we talked about the single-bit adder, and then how we can perform multi-bit addition using a series of single-bit carry adders.
Next we talked about computer memory. Computer memory is like a big long ordered list of numbers. Each number in the list has an address associated with its place in the giant list, so if you know a memory address you can look to see what number lives there. Loading means to read a number from the memory and storing means to put a number into the memory (destroying forever what was in that memory location before).
We also talked about what kinds of information those numbers in the memory can represent. They can be either instructions or data. Data can have any meaning given to it by the person programming the computer. For example a programmer could interpret a binary number in the memory as a few things: the number itself, a specific color, a location on a map, a kind of food, or anything really. It just depends on what the programmer wants for the data to stand for. It's up to the programmer to be consistent with how he treats the data, because the computer itself doesn't care about that at all.
Instructions are the other kind of information that can be stored in memory. Instructions tell the computer's processor what to do next. There's a special register in the processor called the program counter (PC) that tells the processor where, in the memory, its next instruction will come for. The processor fetches (or loads, in memory terms) that instructions, figures out what it says to do, and then does it. After this it moves on tot he next instruction (by increasing the PC) and repeats the process.
Or does it? We also learned about special processor instructions called jumps and branches which directly change the value of the program counter. Jumps unconditionally change the value of the PC to whatever the programmer wants. Branches might change the value of the PC, depending on some condition, like if one variable's value is greater than another variable's value. Once we knew about branching and jumping we could write just about any computer program under the sun, and we looked at an example that shows how we can create a loop using branches and jumps that adds a number to itself several times, essentially performing multiplication.
The last thing we talked about is the register file of the processor. Each processor has a number of registers that are temporary storage for whatever's in the memory, and act as the variables in all of the instructions the processor can execute. The registers don't have addresses the say way that memory locations do, but they still do have distinct names, like $r0 and $r17. Long, complicated programs consist of many loads from memory into registers, additions, branches based on the contents of registers, jumps, and stores back into memory. Even the most complicated programs can be broken down into these elemental pieces.
The last thing we talked about is one other operation that we can perform on registers, and that is the shift. Shifting can be done in either the right or left direction, and these operations are mathematically similar to division and multiplication. The catch is that a single shift operation can only multiply or divide by powers of two. If you want to multiply by numbers other than powers of two, then you need to get more creative. We'll talk about these ways at some future time.
And now we're here. If you missed any posts go back and start from the beginning. I'm trying to build on all of my previous posts, hopefully forming over time one big picture of computer science that anyone can understand.
Tuesday, March 15, 2011
Shifty eyes
Right shift, left shift. These are not just keys on your keyboard. They are the names of mathematical operations that are enormously convenient and helpful in the world of binary math.
First I'll explain what they are, and then I'll explain why they're so helpful. A shift in either direction basically amounts to picking up a binary number, moving it a few places to either the right or left and then plopping it back down. Remember, those "places" in binary numbers are the "2s place," the "4s place," the "8s place," and so on. If you shift a number to the right and some digits get shifted right off the end, then so be it. Similarly, if you shift a number to the left, you have to invent new digits in the low places of that number. Shifting is often represented with these symbols: ">>" for right shift, and "<<" for left shift (see, it's like a double arrow pointing in the direction of the shift).
Here's an example of a right shift of a single-byte binary number:
0b1100 0101 >> 4 = 0b0000 1100
and here's an example of a left shift of a single-byte binary number:
0b0001 1010 << 3 = 0b1101 0000
Do you see how it's like we just picked up the original number and plopped it down in a new place? The right shifted number ended up 4 places to the right, and the left shifted number ended up 3 places to the left.
Here are another couple of examples using decimal that will give you a hint as to why shifting is so helpful in computers:
4563 >> 2 = 45
23 << 3 = 23000
You'll notice in those decimal examples that shifting right by 2 is the same as dividing by 100 (ignoring the resulting remainder or fractions, we're just talking about integers here). Also notice that shifting left by 3 is the same as multiplying by 1000. So now we're starting to see how this is a really nice tool for a computer to have.
Let's look at single-byte binary numbers again and do 2 more concrete examples:
0b1000 0001 >> 1 = 0b0100 0000 (129 shifted right by 1 = 64)
0b0000 0011 << 4 = 0b0011 0000 (3 shifted left by 4 = 48)
Using that exponent notation again from an earlier post, a right shift is like dividing by 2^x (where x is the amount shifted), and a left shift is like multiplying by 2^x (where x is again the amount shifted). When left shifting (multiplying) you need to be careful because you might shift some 1s clear off the end of the binary number, and the result won't really be the correct answer for multiplication. Also, we can only work in powers of two here. If you want to multiply or divide by 3, for example, you cannot do that with a single shift like you can when multiplying or dividing by 2 or 4 (which are powers of 2).
The great thing about the shift operation is that it's so fast. It's even faster and easier than addition to do a in a processor. In our program loop branching example we multiplied 7 by 8, and it took us 8 trips through that loop, adding 7 to a variable each time around. With shifting we can get that same result in a single operation, like this:
0b0000 0111 << 3 = 0b0011 1000 (shift left by 3 because 8=2^3)
And that's it for shifting. I don't have a plan for my next post, but I'll make another one soon anyway.
Monday, March 14, 2011
File it under "register"
That's the best I could come up with, sorry. I'm talking about the title of this post. Sorry.
If you couldn't guess by that awesome title, this post is about the register file. Go ahead and read the title again. Get it? It was pretty good after all, I guess. Anyway, the register file is a part of a computer processor. The simplest way to describe what it is is to say that it's where the variables of a program live when they're not sitting in the computer's memory. The register file is the most temporary of all temporary storage. It is comprised of several "registers," which are just places in the processor that can store a number. If you have a 32-bit processor, then each of the registers in the processor can hold a 32-bit number. It is common for a processor to have from 8-32 (or more) registers.
Data is moved into the registers from memory, some kind of mathematical operation is done with that data, and then the program moves on, putting new data into the register file (the contents of the register file at any one moment doesn't stay relevant for very long usually). If we still need the old data (or the result of some mathematical operation), then we can store the contents of a register back to the memory.
Registers are parts of the computer that can store information, just like memory, however the registers do not have addresses like the memory does. Well, they don't have addresses in the same way, at least, but they do still have a way of telling them apart. Each register has its own name, which is commonly something like $r0 or $r3. The '$' is just convention for saying that we're talking about registers, and then the 'r' is just a further reminder. A 32-register processor would have registers with names from $r0-$r31.
If you'll remember when we talked about branch instructions, all of the branches depended on comparing two different variables to each other, and depending on the comparison, the branch is taken or not. Well, in a real computer we can't just talk about variables as abstractly as that. We have to be more concrete. We have to use registers. A real "branch when x is greater than y" instruction would really look more like this:
bgt $r3, $r4
It's up to the programmer to remember that $r3 really means 'x' and that $r4 really means 'y.'
Load and store instructions are the same way. We don't store 'x' into a memory location, and we don't load into another variable 'y.' Loads and stores look more like this:
ld $r3, 4008 (ld is short for "load")
st 4012, $r4 (st is short for "store")
Every time that you perform some action in a processor, it will involve registers. Are you adding two variables and saving the result in another variable? You're really talking about registers there.
You might think that 8 or 32 registers isn't enough to store all the variables of a program (especially really huge programs like web browsers or word processors). You're right, it's not enough. Most of the variables of a program sit in the computer's memory most of the time. They are only temporarily brought into the registers when they are needed, and then stored back into the memory when they're done. This is happening millions and billions of times every second in your computer right now.
Next time we'll talk about more mathematical operations we can do with binary numbers, but we still aren't going to talk about negative numbers yet. I need to gear up for that one.
Branching example
I'm going to show you a sample of how branching is used in a real program. In this example, I'm going to have several computer instructions, including their instruction addresses. I'm going to follow this format in future examples, so get used to it. The format will be like this:
4: add y, x, 10
Read this as saying that the address for that this instruction is 4 (that is, this instruction gets executed when the program counter is set to 4). The instruction the processor will execute is the add instruction. The next three are numbers or variables. y and x are variables. At any given moment they will have a real value (a number), but a variable's value can be changed. We can replace its old value with a new number. This specific example says to "add x and 10 together, and save the result of that addition in y."
We'll be following the convention that MIPS uses (look up MIPS on Wikipedia if you want more information at this time), where we list where the result of an instruction will be placed first, and then after that list any other inputs we need to compute the result. In this case, the result will be stored in y, and we need the additional inputs of x and 10 in order to complete the add instruction.
Hopefully that was enough to make this instruction format clear. Let's next go through a basic loop in a program. Imagine in this example that going into this loop, x already has the value of 0, y already has the value of 8, and z has the value of 0. I'll just write it out first, and then explain the parts that need to be explained.
(pretend there are instructions before instruction 104 here)
104: add z, z, 7
108: add x, x, 1
112: beq x, y, 120
116: j 104 (j is shorthand for "jump:)
120: (... just pretend more interesting stuff happens after the loop)
Remember in this example, z starts out at 0, x is 0, and y is 8. The add instruction for the z variable say "add z + 7 and store the result in z," and the add instruction for the x variable says "add x + 1 and store the result in x." So each time through our loop we're going to be doing those two things: adding 7 to z, and 1 to x. The branch instruction at 112 says that if x and y are equal to each other, then branch to instruction 120, otherwise, just move on to instruction 116 like normal. If that branch isn't taken, the PC does counts up to 116, and instruction 116 says to immediately jump back to 104, which is the beginning of the loop. This loop continues, each time increasing z by 7, and increasing x by 1, until the branch condition for "x equals y" becomes true, which happens when the loop has executed enough times that x is increased all the way to 8. At this point, the branch is taken and the PC is changed to 120, which is now outside the loop.
One thing you probably noticed is that the instructions are spaced 4 apart instead of just 1 apart. This is because most instructions need to much information to be executed than can be stored in just 1 byte. Again, following the MIPS convention, I've made all instructions 4 bytes long. This isn't how all computers work, but it works well for this example.
So what did this loop do? At the end of it, z is equal to 56, because we're added 7 to z 8 times. In other words, we've performed the multiplication of "8 times 7." I hope this example gives you an idea that you can create really complicated computer programs that are just built out of really simple building blocks.
Next time we'll talk about the register file, which will give more context the structure of processor instructions and give more insight into how computers are physically organized.
4: add y, x, 10
Read this as saying that the address for that this instruction is 4 (that is, this instruction gets executed when the program counter is set to 4). The instruction the processor will execute is the add instruction. The next three are numbers or variables. y and x are variables. At any given moment they will have a real value (a number), but a variable's value can be changed. We can replace its old value with a new number. This specific example says to "add x and 10 together, and save the result of that addition in y."
We'll be following the convention that MIPS uses (look up MIPS on Wikipedia if you want more information at this time), where we list where the result of an instruction will be placed first, and then after that list any other inputs we need to compute the result. In this case, the result will be stored in y, and we need the additional inputs of x and 10 in order to complete the add instruction.
Hopefully that was enough to make this instruction format clear. Let's next go through a basic loop in a program. Imagine in this example that going into this loop, x already has the value of 0, y already has the value of 8, and z has the value of 0. I'll just write it out first, and then explain the parts that need to be explained.
(pretend there are instructions before instruction 104 here)
104: add z, z, 7
108: add x, x, 1
112: beq x, y, 120
116: j 104 (j is shorthand for "jump:)
120: (... just pretend more interesting stuff happens after the loop)
Remember in this example, z starts out at 0, x is 0, and y is 8. The add instruction for the z variable say "add z + 7 and store the result in z," and the add instruction for the x variable says "add x + 1 and store the result in x." So each time through our loop we're going to be doing those two things: adding 7 to z, and 1 to x. The branch instruction at 112 says that if x and y are equal to each other, then branch to instruction 120, otherwise, just move on to instruction 116 like normal. If that branch isn't taken, the PC does counts up to 116, and instruction 116 says to immediately jump back to 104, which is the beginning of the loop. This loop continues, each time increasing z by 7, and increasing x by 1, until the branch condition for "x equals y" becomes true, which happens when the loop has executed enough times that x is increased all the way to 8. At this point, the branch is taken and the PC is changed to 120, which is now outside the loop.
One thing you probably noticed is that the instructions are spaced 4 apart instead of just 1 apart. This is because most instructions need to much information to be executed than can be stored in just 1 byte. Again, following the MIPS convention, I've made all instructions 4 bytes long. This isn't how all computers work, but it works well for this example.
So what did this loop do? At the end of it, z is equal to 56, because we're added 7 to z 8 times. In other words, we've performed the multiplication of "8 times 7." I hope this example gives you an idea that you can create really complicated computer programs that are just built out of really simple building blocks.
Next time we'll talk about the register file, which will give more context the structure of processor instructions and give more insight into how computers are physically organized.
Monday, March 7, 2011
A Fork in the Road
A computer processor will just execute instruction after instruction, all in a row as its program counter (PC) increases, unless it encounters a "jump" or "branch" instruction. A jump or branch instruction directly changes the value of the PC, and therefore it changes where the processor's next instruction will come from. Last time we talked about jump instructions, which unconditionally change the PC to whatever value the programmer wants. This allows the programmer to do things like loop back to execute again instructions that the processor has already executed. In this post we'll talk about branch instructions.
Branch instructions are forks in the road. A branch is a jump instruction with a condition attached. When the processor encounters a branch instruction one of two things will happen. Either the "branch condition" will be met (or in other words, it will be true), or it will not be true. If the branch condition is true, then the branch is "taken," meaning that the jump is performed. In this case the PC gets changed to whatever the branch instruction says it should be. If the branch condition is false, and therefore fails, the branch is "not taken," and the PC is just incremented like normal to the next instruction (PC+1).
There are many kinds of branches, but they all involve comparing two things against each other, and then seeing if some property about that comparison is true. Here are some common types of branches, their associated computer instruction shorthand version, and what they mean in English. The shorthand all starts with "b" for "branch," and the remaining letters give you a hint about what kind of comparison the branch instruction is performing. I'm also going to write two variable names, x and y. Treat them the same as you did in algebra. They're just two numbers, ANY two numbers. Their value isn't important (just like algebra).
beq x,y - branch when x is equal to y
bez x - branch when x equals zero
bgt x,y - branch when x is greater than y
bge x,y - branch when x is greater than or equal to y
blt x,y - branch when x is less than y
ble x,y - branch when x is less than or equal to y
bgtz x - branch when x is greater than or equal to zero
bltz x - branch when x is less than or equal to zero
A lot of those are redundant if you think about it. For example, asking if "x is greater than y" is the same as asking if "y is less than or equal to x." There's no real reason why we need both versions, but having both might make it so that reading computer instructions is easier if you need to debug the code after writing it.
The next post will have a brief example of branching in action, showing a loop from a program that I just made up!
Branch instructions are forks in the road. A branch is a jump instruction with a condition attached. When the processor encounters a branch instruction one of two things will happen. Either the "branch condition" will be met (or in other words, it will be true), or it will not be true. If the branch condition is true, then the branch is "taken," meaning that the jump is performed. In this case the PC gets changed to whatever the branch instruction says it should be. If the branch condition is false, and therefore fails, the branch is "not taken," and the PC is just incremented like normal to the next instruction (PC+1).
There are many kinds of branches, but they all involve comparing two things against each other, and then seeing if some property about that comparison is true. Here are some common types of branches, their associated computer instruction shorthand version, and what they mean in English. The shorthand all starts with "b" for "branch," and the remaining letters give you a hint about what kind of comparison the branch instruction is performing. I'm also going to write two variable names, x and y. Treat them the same as you did in algebra. They're just two numbers, ANY two numbers. Their value isn't important (just like algebra).
beq x,y - branch when x is equal to y
bez x - branch when x equals zero
bgt x,y - branch when x is greater than y
bge x,y - branch when x is greater than or equal to y
blt x,y - branch when x is less than y
ble x,y - branch when x is less than or equal to y
bgtz x - branch when x is greater than or equal to zero
bltz x - branch when x is less than or equal to zero
A lot of those are redundant if you think about it. For example, asking if "x is greater than y" is the same as asking if "y is less than or equal to x." There's no real reason why we need both versions, but having both might make it so that reading computer instructions is easier if you need to debug the code after writing it.
The next post will have a brief example of branching in action, showing a loop from a program that I just made up!
Monday, February 28, 2011
Jump around
From last time you'll remember that computer memory can hold different types of information, namely data and instructions. Both of these are just numbers that are given special meaning either by the programmer (data) or by the computer processor itself (instructions). Last time we talked about how normally the processor reads one instruction, performs the action associated with that instruction, then reads the next instruction, performs it, and on and on. The program counter of the processor holds a number which is the memory address of the next instruction it is going to load for the processor to perform.
Imagine as if all of the instructions of a computer program were in the computer memory all in a row, and the program counter points to the first one, then the next one, then the next. That's pretty much how it works, except that model doesn't allow for the repetition of any instructions (or in other words, the processor can never execute an instruction that has a lower address than its current program counter). It also would mean that you can never skip an instruction that maybe you don't want to do right now. The answer to both of these problems is collectively "jumping" and "branching." A jump is a processor instruction that UNconditionally changes the program counter (and thus the source of the next instruction) to a new value, instead of just the next one in the line. A branch is a processor instruction that conditionally changes the program counter (meaning it may or may not change the program counter, depending on whatever condition the programmer dictates).
We'll talk in a later post about what the difference is between conditional branching and unconditional jumping, but first let's go through an example of regular, unconditional jumping. Let's say your program counter (PC) is currently set to 16 (PC=16). This means that the next instruction that will be executed by the processor is located at memory address 16. The processor loads the instruction at memory address 16, and it finds:
jump 60
This means that executing this instruction directly changes the value of the program counter to PC=60. For the processor's next instruction it looks at memory address 60. Let's say at memory address 60 it finds:
jump 16
This instruction will directly change the program counter to PC=16, which you'll recognize is where it just was last time. This little example is very silly because all it does is jump between PC=16 and PC=60 over and over, like an infinite loop. You would never see this in a real program, but it gives you an idea of how unconditional jumping works, jumping both backwards and forwards. In this example if there hadn't been another jump instruction at PC=60, and instead there had been an add, or load, or store, then the program counter would have just behaved like normal after executing the instruction at PC=60, increasing to the next instruction in the list, and so on.
So in summary, jump instructions directly change the value of the processor's program counter (PC), controlling which instruction will get executed next by the processor. Next time we'll look at conditional jumping, or "branching," and where these conditions come from in the first place.
NOTE: when I say that memory location 16 contains the instruction "jump 60," I don't mean that the word "jump" is somehow written into that memory location. What really is going on is that there is a series of bits that would look pretty random to you or me at first glance, but that the processor interprets as "jump" and then the binary number 60. I'm going to talk about computer instructions in terms of English, not in terms of binary.
Imagine as if all of the instructions of a computer program were in the computer memory all in a row, and the program counter points to the first one, then the next one, then the next. That's pretty much how it works, except that model doesn't allow for the repetition of any instructions (or in other words, the processor can never execute an instruction that has a lower address than its current program counter). It also would mean that you can never skip an instruction that maybe you don't want to do right now. The answer to both of these problems is collectively "jumping" and "branching." A jump is a processor instruction that UNconditionally changes the program counter (and thus the source of the next instruction) to a new value, instead of just the next one in the line. A branch is a processor instruction that conditionally changes the program counter (meaning it may or may not change the program counter, depending on whatever condition the programmer dictates).
We'll talk in a later post about what the difference is between conditional branching and unconditional jumping, but first let's go through an example of regular, unconditional jumping. Let's say your program counter (PC) is currently set to 16 (PC=16). This means that the next instruction that will be executed by the processor is located at memory address 16. The processor loads the instruction at memory address 16, and it finds:
jump 60
This means that executing this instruction directly changes the value of the program counter to PC=60. For the processor's next instruction it looks at memory address 60. Let's say at memory address 60 it finds:
jump 16
This instruction will directly change the program counter to PC=16, which you'll recognize is where it just was last time. This little example is very silly because all it does is jump between PC=16 and PC=60 over and over, like an infinite loop. You would never see this in a real program, but it gives you an idea of how unconditional jumping works, jumping both backwards and forwards. In this example if there hadn't been another jump instruction at PC=60, and instead there had been an add, or load, or store, then the program counter would have just behaved like normal after executing the instruction at PC=60, increasing to the next instruction in the list, and so on.
So in summary, jump instructions directly change the value of the processor's program counter (PC), controlling which instruction will get executed next by the processor. Next time we'll look at conditional jumping, or "branching," and where these conditions come from in the first place.
NOTE: when I say that memory location 16 contains the instruction "jump 60," I don't mean that the word "jump" is somehow written into that memory location. What really is going on is that there is a series of bits that would look pretty random to you or me at first glance, but that the processor interprets as "jump" and then the binary number 60. I'm going to talk about computer instructions in terms of English, not in terms of binary.
Subscribe to:
Posts (Atom)