CS: Loops and conditionals, pt. 2

Sorry this post is coming a bit later than I originally intended. Let's briefly review what we talked about last time before diving into the new material.

Loops and conditionals allow us to control which instructions the computer processor is going to execute and when. Loops let us execute some instructions again, even after we already have executed them. Last time we saw the example of a while() loop that executed the code to add 1 to x and store it in x, and this loop executed 10 times.

Today we're talking about using if() statements to decide if we want to skip over a block of code. If the conditional statement inside the if() statement is true, then the block of code that follows the if() statement is executed. If the conditional statement inside the if() statement is false, then the block of code that follows the if() statement is skipped (it is not executed). Look at this code snippet:

x=1
if(x>2)
{
x=0
}

After the execution of this example the value of x will still be 1 (the value that was set at the beginning of the example). Since x>2 is false (because x is 1, and 1 is not greater than 2), we skipped over the assignment statement that would set x to 0 (x=0). Let's look at an example where the conditional statement evaluates to true:

x=4
if(x>2)
{
x=0
}

Here x starts out as 4, but since 4>2 is true, we execute the block following the if() statement. This block tells us to set x to 0. So at the end of this code snippet, x's final value will be 0.

We can see that if() statements allow us to skip blocks of code that we would only want to execute if the conditional statement of the if() statement is true. Let's look at a more complex example that combines a while() loop, an if() statement and a break:

x=0
y=0
while(x+y<10)
{
if(x<5)
{
y=y+2
}
if(y>4)
{
break
}
x=x+1
}

This example has if() statements inside a while loop. Let's walk through what happens here. First of all, both x and y are set to 0, and then we look at the while loop. Since x+y=0 right now, and 0<10, we will execute the while loop at least once, so let's jump into it. The first thing we run into inside the while loop's block is an if() statement, which asks if x is less than 5. This is true right now, so let's execute that if() statement's block, which increases y by 2. At this point, x is still 0 and y is now 2. Now we look at the next if() statement, which asks if y is greater than 4. This is not true, so we'll skip that block for now. Next we add 1 to x and store the result in x. We've now gone through the loop one time, and x is 1 and y is 2.

What do you do when you finish a run through a while() loop? Go back to the top and test to see if you need to do it all over again. We go back to the top and test x+y<10. Right now x+y is 3, which is definitely less than 10, so we should execute the while() loop's block again. Again we run into the if(x<5) statement, and again this is true, so we execute y=y+2, so now y is 4. Next we test to see if(y>4). Since y is exactly equal to 4, it is *not* greater than 4, so this conditional statement is still false, so we skip the contents of that block. Finally we execute x=x+1, and we're done with our second run of that loop. At this point, x=2 and y=4.

We again go back to the top of the loop, x+y is still less than 10, so we execute the loop one more time. if(x<5) is still true, so we execute y=y+2 again, making y equal to 6 now. This time when we execute the if(y>4) statement, y *is* greater than 4, so we execute the break statement. A break statement means "you're done with this loop now, so exit it immediately without doing anything else on your way out." After executing the break we're now outside the loop and we're done with our code snippet. The final score has x=2 and y=6. Notice that if it weren't for the break statement, since x+y<10 is still true we would still be going through our while() loop until such a time as when x+y is greater than 10.

You might need to read through the examples here a few times. It's substantially more complicated than anything I've presented lately, so you should take your time and go slowly. Make sure you get it.

Next time I'm probably going to talk more about consumer advice. Some time in the future I'll talk a little bit about electricity, just because someone was curious, but I remind you that I am not really qualified to explain it. Good luck to me writing that and you reading that.

CS: Loops and conditionals, pt. 1

When I set out to write this series of articles, I wanted to help people who use computers, but don't understand what's going on under the hood, understand what's going on under the hood. Before the reset a couple weeks ago I talked about binary math, computer memory, and branching, in that order. This time around I've skipped binary math, I've talked about memory from a high, abstract level, and now I'm going to tackle branching/looping again. Instead of presenting simple programs as short assembly instruction sequences like I did last time, I'm going to take the easy way out and use a format that might resemble a regular programming language. With that out of the way ...

Everything a computer does can be broken up into individual, small and distinct operations called "instructions." Instructions are simple units of work, and a single instruction might say "load the variable at this memory address into the processor," or "add these two variables together and store the result in this other variable." These instructions are stored in memory and the processor tackles these in the order they appear in memory (for example, it executes the instruction at memory address 200 before it executes the instruction at address 201, and both of these are done before the address at 202, &c.).

Performing instructions in order is useful because it lets the programmer have guarantees about what the processor will do when it executes the program (he knows it won't just randomly execute whatever it feels like). The immediate downside is that if the computer keeps executing instructions in a straight line, there's no way to re-execute old instructions again, or to skip instructions maybe you don't want to execute right now. Both of these problems are solved via looping and conditional execution.

First a bit of vocabulary. I'm going to refer to the endless, ordered list of instructions the processor can execute as the "instruction stream." In this context, "looping" means to repeat an earlier part of the instruction stream (perhaps many times) and "conditional execution" means that you *maybe* will execute the next part of the instruction stream, or you might skip it.

Next we need to be familiar with some computer language jargon and notation relating to loops and conditionals. Here are some more vocabulary words to remember:

conditional statement - This is a question that you can ask about the current state of the program and its variables that you can either answer with "true" or "false." For example, you can ask "is variable X is greater than 10?" As a conditional statement that would be in a real program, this would appear as "X>10" (note there is no question mark, and we're using the "greater than" symbol). If X is greater than 10, this will mean "true," and if X is 9 or less, then this will mean "false." It's conditional.

while() - Yes, the parentheses are included in this vocabulary word. Inside the parentheses goes a "conditional statement." If the conditional statement is true, then you perform some loop as long as the conditional remains true. If the conditional was never true (i.e., always false), then you skip over the while-loop altogether.

if() - Yes, again the parentheses are included, and there's another conditional statement in there. This is really similar to a while-loop, except instead of repeating what comes after this over and over as long as the condition is true, you execute it only once if the condition is true, or zero times if it is false.

{} - These braces let you know that all of the instructions between them are grouped together. This is called a "code block" ("block" as in a block of a street, where all of the houses on that block are neighbors). This group of instructions is what gets repeatedly executed in a loop, or what might skipped over entirely if an if-statement evaluates to false.

break - this special command lets you get out of a while loop early. It usually shows up right after an if-statement. We'll see one of these in action in the next article.

Before I end this article I want to show one example of a simple while loop that is executed 10 times (I parenthetically explain each line. Don't get confused by too many parentheses):

x=0 (this means we're making the variable x hold the value 0)
while(x<10) (execute this loop as long as x is less than 10)
{
x=x+1 (this means we're taking whatever x currently holds, adding one, and making x hold that new value. Essentially we're increasing the vale of x by 1)
}

Variable x starts out at 0, and 1 is added to it 10 times. This is a while-loop that loops around 10 times (or 9 if you don't count the first time through as a "loop"). Notice the braces, also. This time there was only one instruction inside the braces, but there could have been more. If there were more, they would each be on their own line, and each would get executed in the order it appears. When we loop, we go back to the very beginning of the loop, to the very first instruction if there is more than one in the code block.

That's it for this time. Next time, I'll show an example using if-statements, and then one big example that incorporates a while-loop, if-statement, a code block that's bigger than 1, and a break command.

CONSUMER ADVICE: How much RAM?

When buying a new computer, the single most important thing for the average consumer to consider is how much RAM their computer will have. RAM is short for Random Access Memory, but that is neither here nor there--most people don't need to know/care about that. What RAM means to the typical consumer is that more of it lets your computer "feel faster." Well, up to a point.

I suppose this requires a little bit more explanation. In computers there are two types of data storage that make the biggest difference to consumers--hard drive space and RAM. The hard drive holds your permanent data that will stick around long after you've turned your computer off (it will still be there when you turn it on the next time, too). The hard drive holds your photos, music, movies and programs, any and all of which you *can* use whenever you want. The more hard drive capacity you have, the more stuff your computer can permanently store. Hard drives have incredible capacity but they are very, very, very slow. They are slow because they have mechanical moving parts that have to physically spin around to access your data. It's a tradeoff.

RAM, on the other hand, contains what your computer *is* working on *right now*. It's like temporary storage for your computer's current needs. Unlike a hard drive, RAM has no moving parts and its speed is only limited by the speed that electricity can flow through wires and that logic chips can act fast enough to control it. In other words, it's way faster than a hard drive. Unfortunately, it also has much less capacity than a hard drive. This low capacity can be a problem.

If you are running a heavy workload on your computer, it's possible that not everything you're working on will fit inside your RAM. If this happens, then some of what you're working on will spill over to your hard drive (which will definitely have enough space). This spilling over effect makes your computer *feel* very, very, very slow because your hard drive *is* very, very, very slow. This is what is going on when most people say their computer "feels slow." It feels slow because it *is* slow.

So what's the solution? The solution is to buy *enough* RAM. "Enough" is the key word here. You need to buy enough RAM to fit all of the programs and movies and photos you want to work on at the same time without spilling over into the hard drive. Buying any more than just "enough" RAM will probably be a waste of money, because that extra RAM will go unused. But how much is "enough?" Well, I can't tell you exactly how much you personally will need, but I can give you some good general guidelines that should suit the Average User.

If you are buying a new computer right now (April 2011) I would recommend to not get less than 3GB (giga bytes) of RAM. Any less than this and you will probably run into that "slow feeling" occasionally during normal use. 4GB of RAM would be even better, but if you are buying a system that you want to last more than 2 years, I would recommend getting a computer with 6GB or 8GB of RAM. The good thing about buying more RAM is that it's a pretty cheap upgrade that can go a long way toward making your computer "feel fast." Buying 12GB or more is probably overkill at this point in time, but if the price is right or you expect you will use it (like if you are a graphics or movie editing professional) then it's probably worth it.

Of course there are many aspects to a computer that consumers need to be aware of when choosing what to buy, and I've only scratched the surface here. I feel like I did start with the most important aspect, though. Buying "enough" RAM (whatever that means) is the best thing you can do for making your computer feel fast, and is honestly the first thing you should look at on a specifications sheet when shopping for a new computer. Don't skimp!

CS THEORY: Variables and memory

The last time I used the tag "CS THEORY" I didn't really talk about CS theory at all, did I? All I talked about is that there are memory cells and they have numbers in them. That's fine, but it didn't quite make it into the realm of CS theory. In order to do that, we need to talk about what a memory can DO, not just what it is.

As far as "what it is" goes, it's just as I've already said. It's a giant list of cells, each of which can each hold a number. That's not very interesting. What's more interesting is how the numbers get there, and what happens to them once they are there. There are two interesting aspects of memory cells that I'm going to talk about today.

First, memory cells are useful because they each have a unique identifier, and that makes it possible to not get mixed up about what numbers you're storing where. In the memory of a computer, each memory cell has a unique number associated with it called an "address." In a typical computer today its memory will have addresses 0 through about 4 billion. This means there are 4 billion different memory cells where you could store a number. Every time you talk about memory cell 2,361 you're going to be talking about the same memory cell. It didn't go anywhere since the last time you used it.

Second, memory cells in a computer are useful because they are reliable. If you put a number into a memory cell, it will stay there forever, or until you put a different number there. You don't need to worry about the contents of the memory cell accidentally disappearing. That doesn't happen. If it did randomly happen that your data could just disappear, then you wouldn't have a very reliable or useful computer. You couldn't trust it to do anything correctly. Computers are built upon the assumption that this doesn't happen, and that you can always get out of a memory what you put in earlier.

These two properties of computer memory allow us to do real work with our computers. In programming languages that are used to program computers, we often use variables to represent memory cells. Instead of talking about "memory cell 2,361" the programmer will just type "X" (or any other name he dreams up) and it means the same thing. I just pulled the number 2,361 out of the air. It doesn't matter what the address is.

In fact, the programmer doesn't even need to ever know what real address variable X refers to. The programmer can just logically reason about made up variables like X and Y and Z, and while ultimately in the computer these variables will stand for memory cell addresses, the programmer doesn't ever need to think about that. The programmer can type "Add X and Y and store the result in Z," and that might get translated by the computer into "add the contents of memory cell 2,361 and memory cell 7,841 and store the result in memory cell 451." This is called abstraction. The programmer thinks about pretend variables and lets the computer worry about how it will physically carry out the math the programmer has asked it to do by manipulating real memory cells that are physically somewhere in the computer.

Today we talked more about computer memory, how every cell in a computer memory has an address, and how what you put into a memory will stay there and won't just disappear on you. These properties make it very convenient to write computer programs, even without having to know how memory cells really work. Programmers can just abstract away all those complicated details and play with raw, abstract variables instead.

I think for my next post I will give some consumer advice. Next time we talk about CS theory I think I will talk about C-like assignment statements, conditional statements and loops.

CS THEORY: Memorable numbers

See, I told you this would be the title of the next article.

I've decided to start with something that is more fundamental to computer science, and less fundamental to computer architecture. I think talking about the concepts behind computer memory from a theoretical, mathematical kind of perspective will be more valuable to more people when starting out than talking about binary mathematics. So for now, I'm not going to talk about binary numbers (although you're welcome to imagine all the numbers I do talk about as such if you like). Instead, I'm going to talk about regular numbers and memory cells.

I kind of struggled with how I wanted to explain computer memory this time. Last time I talked about a lineup of bathtubs filled with binary digit buckets. That was pretty weird, in retrospect. Let's move away from that and talk instead about regular numbers and boxes that can hold those numbers.

Imagine a spreadsheet. Imagine the giant grid that extends on forever to the right and down, with the alphabet along the top naming each of the columns, and the numbers along the side naming the rows. Now, erase columns B-infinity, so we're left only with column A. This is a pretty good way to visualize computer memory. A single, numbered list of boxes that can each hold a number. It doesn't really make a difference whether you imagine this numbered list of boxes as being vertically or horizontally oriented, but for the sake of space efficiency, I'm going to write it out as a horizontal row of boxes of numbers. Here it is:

[_] [_] [_] [_]

Imagine that as 4 boxes, none of which currently has a number in it. I just got tired of typing those out after 4 boxes, but in real computer memory there are billions. Yeah, billions. That's a lot. One of the things about these memory boxes, or "memory cells" as I'm going to call them, is that they *need* to hold numbers. They can't actually be empty. So let's put some numbers in there:

[83] [101] [116] [104]

Pretty good numbers, right? Let's list some things we could do with those numbers. Well, we could add two of them together, we could multiply two of them together, we could do any kind of math on them that we want. Those are pretty predictable uses of numbers. One thing about computers, though, is that the computer doesn't care what we do with those numbers or what we pretend those numbers mean (unless we ask the computer to do math on those numbers, then the computer will treat them as numbers and do the math correctly).

In fact, those numbers I listed up above are not totally random. There is a way of pretending that numbers are actually letters and symbols called ASCII that says that those numbers I chose up there actually stand for something else. According to ASCII, the 83 stands for 'S', the 101 stands for 'e', the 116 stands for 't' and the 104 stands for 'h'. So [83] [101] [116] [104] can actually stand for "Seth" (that's my name, by the way).

Now to relate this to the computer you're reading this on right now. Your computer has billions of memory cells, each with some kind of number in it, and those numbers can mean things that humans can understand, like letters we can read, or colors we can see, or sounds. Since I typed out this word "Seth" and your computer downloaded this webpage so it could be displayed on your screen, somewhere in your computer's memory is the sequence of numbers: [83] [101] [116] [104].*

From today's article I hope you got an idea that there is a series of memory cells in your computer and each cell holds a number in it. These numbers can be meaningful to humans in ways other than just how we understand numbers as numbers. We used the example of the ASCII encoding for the word "Seth" as a way to understand how a series of numbers can really be understood as a series of letters we can read.

Next time we talk about CS THEORY we'll talk about how memory cells are organized.

*Ok, so this webpage was probably encoded with some other number-to-text system than ASCII, but you get the point.

Next time, on ...

Hey, everybody. I haven't made any updates in the last week or so. I recently heard from a couple of smart people who have read through my posts so far that I'm not doing a good enough job of explaining everything plainly. Because of this, I'm going to do a "reboot" of this series of articles on the basics of computer science.

In writing this series I was attempting to do the opposite of what is usually done in computer science education. Usually, you start with the basics of creating a working computer program in a computer language like C or Java, and then eventually reveal the details under the hood that allow that program to be run on the computer.

I was trying to do the opposite of this, and talk about how things like binary math and computer memory work without giving them any context or enough explanation. In my reboot, I'm still going to do this, but I'm going to interleave a few different types of topics as I go. I'm also going to re-write on some of the topics I've already covered, trying to give them a better treatment than I did the first time. I'm not going to erase anything that has come before, because I think I have written some good things there, that maybe you should revisit as a reader after I've given more background.

Like I already mentioned, I'm going to discuss topics under large umbrella topics. At the beginning of each post title I will say in capital letters which of these umbrellas that post falls under. For example, my first post "Of bits" would be named "MATH: Of bits" under this new naming convention.

So that's the plan moving forward. I think the first thing I will talk about with this new plan will be titled "CS THEORY: Memorable numbers." I'm going to forget talking about binary numbers until later, and just focus on the basic concept of what computer memory is and what it does.

I've also received a request to talk about more electricity-oriented topics (digital circuits and whatnot). I am not very well qualified to explain the circuits that make computers happen, but I will take a stab at it after I have read up on the subject a little more. Until next time.

Two's complement examples

My friend suggested that I should talk more about one's complement and endianness. I think that endianness is confusing, so I don't want to talk about it, other than to say that it deals with the order of bytes in a multi-byte number in memory (click the link if you want to get confused more). I will mention one's complement, though, because I think it's interesting.

Two's complement is the system where in order to turn a number into its negative you flip all the bits and add one. One's complement is similar, except you don't add one at the end of the number conversion. For example, in one's complement the number -11 would be represented like this:

0b0000 1011 (that's positive 11)
flip all the bits
0b1111 0100 (and that's -11 in one's complement)

This looks a lot easier, right? Well, the downside is that there's an additional step when adding negative numbers with this representation. After you do the normal addition, you have to look at the final carry-out and add that value back to the one's place of your result. That right there isn't that big of a deal, and adders could be built to automatically do that.

The other bad thing about one's complement is that it's possible to have both positive and negative ZERO. Both 0b0000 0000 and 0b1111 1111 mean "zero" but one of them is positive and one is negative (remember to look at the sign bit to determine whether it's positive or negative). That's weird and it means that we can only represent 255 numbers with a single byte instead of 256 that we can represent using two's complement.

I'm not going to do any examples of one's complement, because it isn't used in real life. Instead, I'm going to do a couple examples of two's complement. First, let's transform positive 56 into negative 56, and back again. I didn't mention it last time, but you can tell the value of a negative two's complement number by repeating the same steps that made transformed it from positive to negative in the first place. Like this:

0b0011 1000 (+56)
flip all the bits
0b1100 0111
and add 1
0b1100 1000 (now we have -56)

Now let's turn that negative number back into a positive:

0b1100 1000 (-56)
flip all the bits
0b0011 0111
and add 1
0b0011 1000 (and we're back to +56)

Now let's subtract 15 from 32 (32-15=?).

Here's 32:
0b0010 0000 (+32)

Now let's figure out what -15 is:
0b0000 1111 (+15)
flip all the bits
0b1111 0000
and add 1
0b1111 0001 (-15)

Now we add them together, because 32 + (-15) is the same as 32-15.

+0b0010 0000 (32)
+0b1111 0001 (-15)
=0b0001 0001 (17)

This time we're going to totally ignore the final carry-out. Look at the sign bit, and notice that it's a 0, that means we ended up with a positive number. In fact, that number we ended up with is 17, which is the right answer. 32-15=17.

Just to review, this is how subtraction is accomplished in real computers, and how negative numbers are represented in real computers. We use two's complement because it lets us represent a wide range of positive and negative values (it doesn't have that silly +0/-0 issue one's complement has), and it is terribly, terribly convenient for allowing us to use regular multi-bit adders to perform subtraction.

I don't have a plan already in my head for what to present next, but if you ever have a recommendation, let me know in the comments.

Two's compliment

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.

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.

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.

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.

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!

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.

Remember these things

We know computer memory is a big long list of bytes that can be read and written (loaded and stored), but now we need to talk about the types of information that is contained in the memory. There are two broad categories of information that the computer keeps track of, namely, instructions and data. Both of these are just numbers when you get right down to it, because that's all the memory can hold in it, so the difference between them lies in how the computer treats these different kinds of information.

Let's talk about data first. The word "data" is the plural form of the word "datum," which just means "piece of information." So "data" means "many pieces of information." All data in a computer is represented as binary numbers, but those binary numbers can stand for a variety of different things. It just depends on what meaning the computer's programmer decides to give those binary numbers (which the computer doesn't really care about, by the way). The programmer could consider the byte 0b0001 0001 to mean the decimal number 33 or the ASCII symbol '!' (ASCII is just a standard convention for treating single-byte numbers as text symbols). It is very common for things we want to represent in a computer to take up more than one byte. For example, numbers larger than 255 must be represented by more than one byte. Also, picture and movie files are larger than one byte. Large quantities of text can be represented by very long lists of single bytes that are interpreted as ASCII symbols (like the example above). In the end, it is the value of the byte(s) and the context which the programmer gives them that really determines what the data in a computer memory means.

The other kind of information that can be stored in computer memory is computer processor instructions. I know we haven't talked about how computer processors work at all yet, but I think this one detail about their operation cannot be avoided at this time. Processors work by reading a part of the computer memory, and then depending on what was contained in that part of the computer memory (or that "instruction"), the processor will perform an action. There is a counter in the processor called the "program counter" which keeps track of the place in memory that the processor will get its next instruction. After every instruction is processed the program counter gets increased (i.e., "counts up") to move on to the next instruction. After that instruction is processed, the program counter "counts up" again, moving on to the next instruction, and so on.

Just like how data is just a series of arbitrary bytes until the programmer steps in to give those bytes meaning, instructions are just series of arbitrary bytes until the processor's designer steps in to give those bytes meaning. There are many different types of instructions, including adding, loading, storing, jumping and branching. There are also many more, but these are the basic building blocks of computer science that we're focusing on for now. We've already talked in detail about adding, loading and storing.

Jumping and branching are special instructions that deal with changing the program counter. Normally the program counter just increases (counts up) to the next instruction after each previous instruction is completed. This doesn't allow for repeating any previous instructions (or looping, as it's called in programming). Jumping and branching allow for the program counter to be set to whatever value the programmer wants. This can include increasing the program counter, or decreasing it. Next time we'll talk more about jumping and branching and what it allows computers to do that would otherwise be impossible.

Note: Yes, I know that I was inconsistent about treating the word "data" as a plural word. This is pretty much universal in all technical and academic literature. Even though the word represents a plural concept, it is almost always treated grammatically as a singular. I will be following this convention from here on out.

Bathtubs are memorable

I'm going to get right to the point. All that nonsense about lined up bathtubs full of buckets? I made it up. I was trying to teach symbolically. Did it work?

Anyway, here's the breakdown. In that metaphor, the lined-up bathtubs collectively represent the memory system of a computer. The bathtubs represent individual bytes, and the buckets in the bathtubs represent individual bits. The numbers? Those were numbers. It would have taken too much imagination on my part to invent a replacement for numbers.

So am I trying to tell you that the memory system of a computer is a giant series of bytes full of bits? Pretty much. That's not how it's physically implemented in the computer (have you ever noticed that memory chips are square-ish, and not 3 meters long and impossibly thin?), but we're not quite ready to talk about the physical implementation of computers yet.

As for the loading and storing, I pretty much just explained that one directly also. There are fundamentally two things that a computer can do with its memory system. It can "load" values out of it, and you can "store" values into it. I know, it might seem like "load" should mean "put something into the memory," but remember that when a number is "loaded" out of the memory, it's "loaded" into somewhere else. Yeah, that doesn't really cut it for me either, but remember that the opposite of "load" is "store," and that sounds even more like you're storing something into the memory (and this time you really are).

All of the bytes in a memory system are numbered. There's an order, and all of the bytes in memory have an "address." The computer loads numbers out of a particular address, and stores numbers into other addresses. A computer might "store 128 into memory address 183,820,"or "load memory address 1,024 and put its contents into variable X." One of the basic things that makes this a reliable system to use is that the contents of the memory system cannot change unless the computer explicitly changes it. That allows us to confidently store numbers into the memory and get the same number back out when we load it later.

Just to recap, a computer's memory system consists of a very long string of bytes that hold their value between accesses. These bytes can be accessed using a specific numbered address for each byte. These accesses can be loads or stores. Loads read numbers out of the memory, and stores put numbers into the memory.

Next time we'll talk about what kinds of things are stored in memory, in preparation for explaining our last big ingredient to building a working computer: branching.

Thanks for the memories

I apologize for the all-too-long post last time. It probably should have been two posts. Today, however, I want to paint a mental picture.

Imagine you are in an empty void, floating high above what looks like a thin, straight line starting directly beneath you, but stretching on extremely far ahead of you. You are slowly floating down to where this line begins. As you get closer, you notice that the line is not as narrow as you first had supposed. You get closer still and notice that this entire line is comprised of a series of bathtubs. These bathtubs each have a sign next to them with a number. The one directly below you is marked "0." Next to it is bathtub "1." The furthest you can read with your naked eye seems to be bathtub "23," but you can tell that all of the bathtubs in the line have increasing numers the further away they get from you, so you assume the numbering system just continues on forever.

You finally touch down next to bathtub "0." Strangely enough, this bathtub is not full of water or even Jell-o, but rather it is full of buckets. 8 buckets right in a row. Of course you assume that the buckets are full of Jell-o, but this isn't the case either. The buckets have numbers in them, single binary digits, one digit per bucket. 8 digits per bathtub. Some buckets have 0b0, and some have 0b1.

These bathtubs do not have regular faucets to fill them with water. Instead, where the faucet should be, there are two buttons. One is marked "load," and the other, "store." You look around, and finding yourself alone decide that it wouldn't hurt anyone to try out these buttons. You reach out with your left hand and timidly press the load button of bathtub 0. Electricty runs through your left hand, up your arm, across your body and down to your right hand, where suddenly appears the binary number 0b1101 1000 floating above the palm of your right hand. Don't worry, it doesn't hurt. You notice that this is the exact same binary number that is in the bathtub. It's as if the load button copied the value of the bathtub into your hand.

You next try the store button. Again, electricity runs through your body, this time from right to left, but the value of bathtub 0 remains unchanged. That's odd. Next you decide to try an experiment where you load the value of one bathtub, and try to store it somewhere else. You press load again on bathtub 0, and again the value 0b1101 1000 appears in your right hand. You move to bathtub 1, which has the value 0b0000 0000, and press its store button. Suddenly bathtub 1's value changes to match the value in your hand, and the value that was in bathtub 1 is lost forever. After some more experimentation of loading values from various bathtubs and storing them into other bathtubs, you start to reach the limits of how much fun you can have with this.

It gets boring moving numbers around if that's all you can do. You start wishing you could do something else with these numbers. You wish you could at least add them together (see, I told you addition was going to be important), and do something interesting with the loaded numbers before you store them away again.

And then you wake up. Or something. I'm not very good at endings for dream sequences. Next time we'll talk about the interpretation of the dream, and what these bathtubs and buckets have to do with real computers.

"What does it mean?" and addition examples

With a knowledge of carry bits and single-bit adders, we are ready to dive into some examples of binary addition. Sounds pretty fun, right? Well, I know it does, but before we get into that I want to comment on why we're spending so much time talking about things that might not seem very important.

You came here wanting to learn about computer science and how a computer does what it does, right? Well, believe it or not, the addition of two numbers is a very, very important part of computers. In fact, there are only two more big things you need other than addition in order to have a fully functioning computer. If you create a computer that can add two numbers together (including negative numbers, which we'll get to another time), can "branch" and "jump" (basically, this means handling if-then statements and loops), and has a memory system (meaning there are places you can store data and retrieve it later), then you can program that computer to do anything you can think of. You can program video games, word processors, web browsers or anything else. It's kind of crazy that such complex programs have been created out of such simple building blocks.

Of those extremely basic building blocks of computing, I decided that talking about adders and the binary number system was the easiest and best place to start. A working knowledge of adders and binary will make learning the other concepts far easier. This is all in stark contrast to how computer science is most often taught in the world. It is far more common to start teaching computers with high-level computer languages that hide all of the important details about how computers work. You should consider yourself lucky that I trust you enough to start with the important stuff, saving the boring high-level stuff for later.

Speaking of important stuff, let's get back to examples of 8-bit binary addition. Let's first look at an example where none of the single-bit adders do any carry-out or carry-in (sorry for the poorly formatted text in these examples, I'll figure it out eventually):

+0b1100 1100 (204 in decimal, that extra + at the beginning is just to get the text to line up)

+0b0011 0011 (51)

=

+0b1111 1111 (255)

For each bit of the answer we are adding only 0b0+ob1, giving us 0b1 for the result bit. Now for an example that uses carry:

+0b0000 0111 (7)

+0b0000 0011 (3)

=

+0b0000 1010 (10)

We had to use carry for the "ones place," "twos place," and "fours place." The addition for the "eights place" consisted of 0b0+0b0+0b1 (that last 0b1 being the carry-in from the addition of the "fours place"). Let's look at one more extreme case of carry in action:

+0b1111 1111 (255)

+0b0000 0001 (1)

=

+0b0000 0000 (???)

This makes it look like adding 1 to the maximum value of a byte (255), will result in 0 as the answer. What's really going on is that the true answer (256) cannot be represented by only 8 bits. It is impossible. The true answer consists of 8 bits of 0, and the final carry-out bit set to one. When addition results in carry-out beyond the limits of what the answer can store, we call this "overflow."

This means that the answer that's in the remaining 8 bits is not the right answer, and that you messed up by trying to add two numbers that were too big for the number of bits you wanted the answer to fit in. The best thing to do in this case is to add two 16-bit numbers together, because then you will have the ability to represent the number 256 without any problems. You can convert an 8-bit number to a 16-bit number by just adding extra 0s to the front of it. This is what that addition then looks like (again, sorry for the horrible formatting):

+0b0000 0000 1111 1111 (255)

+0b0000 0000 0000 0001 (1)

=

+0b0000 0001 0000 0000 (256)

In this day and age when we have 64-bit adders at our disposal it is very rare to add numbers together that are too big to fit into the result bits and cause overflow, unless you're doing something weird or wrong (or you're a scientist). Next time we'll take a break from adding binary numbers, and talk about computer memory. However, we're not totally done with addition yet, as we still need to cover subtraction, which is a just special form of addition with negative numbers.

Carry out, carry in

We've covered addition for two single bit binary values, and how the outcome of that addition is stored in the result bit and the carry-out bit. In a real computer's binary adder, the addition of two (and only two) values only happens for the least significant bit of the binary number (or the "ones place"). For the rest of the bits, we have to add three different values together: the two bits being added like before, plus the carry-in bit, which is just the carry-out bit from performing addition on the bits we just added together (moving right-to-left, like the decimal addition we're used to).

The carry-out of addition is handed to the carry-in of the adder for the next higher bits, so that they can use it to perform their addition. The "ones place" carry-out becomes the carry-in for the "twos place," and the carry-out of the "twos place" becomes the carry-in for the "fours place," and so forth (remember, this is binary, so our places are: 1s, 2s, 4s, 8s, 16s, etc.). The "ones place" is the only place that doesn't use any carry-in at all, because there is nothing lower than the "ones place" that the carry-in could have come from.

When we consider the carry-in bit there are suddenly twice as many options for combinations of inputs to our single-bit adder. Here are all of the combinations:

0b0+0b0+0b0: result=0b0, carry-out=0b0

0b0+0b0+0b1: result=0b1, carry-out=0b0

0b0+0b1+0b0: result=0b1, carry-out=0b0

0b0+0b1+0b1: result=0b0, carry-out=0b1

0b1+0b0+0b0: result=0b1, carry-out=0b0

0b1+0b0+0b1: result=0b0, carry-out=0b1

0b1+0b1+0b0: result=0b0, carry-out=0b1

0b1+0b1+0b1: result=0b1, carry-out=0b1

Even though there are twice as many inputs, there is only one single more output (result=0b1, carry-out=0b1). This is the one combination that cannot be seen from adding together two (and only two) single-digit binary numbers. Notice also that whenever at least two inputs are 0b1, then the carry-out will be 0b1 regardless of what the third input is. Also notice that the result bit is 0b1 only if there is an odd number of 0b1 values among the inputs. Interesting.

Multi-bit adders are created by stringing together many single-bit adders, feeding the carry-out of one directly into the carry-in of the other. When adding two binary numbers together, one number plugs in each of its bits into one input of each single-bit adder, and the other number plugs its bits into the other input of each single-bit adder. After the electrical circuit that comprises the adder has a chance to stabilize, the answer of the addition will appear in the result bits of single-bit adders, plus one final carry-out at the far end. You can make an 8-bit adder by stringing together 8 single-bit adders in this way, and the result will be 8-bits long, plus the carry-out (so really 9-bits long).

Next time we'll show examples of multi-bit binary addition in action, and I might even explain sometime soon what all this has to do with computer science.

Adding single bits

Today we'll look at what it's like to add two single-digit binary numbers together. Each of the two single-digit binary numbers can either have the value 0b0 or 0b1. Considering both bits together, this means there are 4 different possible combinations of input for single-bit addition ((0b0+0b0), (0b0+0b1), (0b1+0b0), and (0b1+0b1)). Here are the results for all of those additions:

0b0+0b0 = 0b0 = 0

0b0+0b1 = 0b1 = 1

0b1+0b0 = 0b1 = 1

0b1+0b1 = 0b10 = 2

The result for each of those additions can be represented by a single result bit EXCEPT 0b1+0b1, which results in the 2-bit number, 0b10 (the decimal number 2). This leads to a very important observation. When adding two binary numbers, it is possible that the resulting number will require 1 more bit to store the result than either of the inputs. Possible, but not guaranteed to need it. It's exactly the same as in the decimal number system. Adding two single-digit decimal numbers might result in a single-digit answer, as in the case of 2+2=4, or it might result in a two-digit answer, as in the case of 7+8=15. You can never require 3 result digits when adding two single-digit numbers, as 9+9=18 (the result of 9+9 is the largest possible number you can get from adding two single-digit values).

So we know that the addition of two single-digit binary numbers may or may not produce a two-bit result, but what if it does? What does a real computer do with that? In a real computer binary adder, the second bit of the answer is called the carry-out bit. The first bit is called the result bit. When learning arithmetic in elementary school, we are taught about the carry-out bit, or rather the carry digit. When you are adding two numbers you might get "8+6=four carry the one, for a total of fourteen." It's the exact same thing with single-bit binary addition. Let's look again at previous additions in the context of result bits and carry bits.

0b0+0b0, result bit = 0, carry-out bit = 0

0b0+0b1, result bit = 1, carry-out bit = 0

0b1+0b0, result bit = 1, carry-out bit = 0

0b1+0b1, result bit = 0, carry-out bit = 1

So if there's a carry-out bit, does that mean there's a carry-in bit? There is, actually, and it is instrumental to multi-bit addition, which we'll talk about next time.

More on binary

I guess before we can talk about how easy math is to perform on binary numbers, we need to first understand a little more about how binary numbers themselves work. We talked earlier about how a byte can range in value from 0b0000 0000 to 0b1111 1111, and how this corresponds to the range of values in decimal of 0 to 255. Let's break it down a little bit more thoroughly to see how binary numbers are constructed.

Decimal numbers are comprised of several digits, or "places" as you may remember them being called in elementary school. We have the "ones place" the "tens place" the "hundreds place" and so forth. So the number 453 means four "hundreds" five "tens" and three "ones." The number 307 means three "hundreds" zero "tens" and seven "ones." Binary numbers work the same way, except instead of having "ones," "tens" and "hundreds" (which you will notice are all numbers that can be described by 10^(x)), we have "ones," "twos," "fours" and so forth (all of those places can be described as 2^(x)). Another big difference between decimal and binary is the range that each digit can take on. In decimal, digits can range from 0-9 (ten different options for the base-ten, or decimal, number system). In binary, digits can only be in the range 0-1 (two different options for the base-two, or binary, number system).

Let's take a quick look at a few examples that might cement the differences between decimal and binary in our minds.

In decimal we have such numbers as:

1 = one

10 = ten

100 = one hundred

1000 = one thousand

In binary those same symbols mean something very different:

0b1 = one

0b10 = two

0b100 = four

0b1000 = eight

Let's look at one more concrete example, the difference between the decimal number 1101 and the binary number 0b1101. In decimal those symbols mean one "thousands" one "hundreds" zero "tens" and one "ones," for a total of one thousand, one hundred and one. In binary those symbols mean one "eights" one "fours" zero "twos" and one "ones," for a total of (8+4+0+1)=thirteen. Each successive place (moving left as you're reading a binary number) means another power of two. Here's a list of the powers of two leading up to 2^8: 1, 2, 4, 8, 16, 32, 64, 128, 256 (remember, those are their decimal representation). Those are all of the powers of two we'll need for our discussion next time on binary arithmetic.

Also, bytes

A single bit can represent two distinct "things," as we talked about in the previous post, but what about collections of bits? How many things can 2 bits represent? 8 bits? 1000 bits? 0 bits? The formula to figure this out is given by the exponential formula 2^x, where x is the number of bits. The caret symbol denotes that what follows should be considered as superscript, so 2^x means "two raised to the x power." A single bit gives you 2^1=2 things you can represent. 2^10=2x2x2x2x2x2x2x2x2x2=1024 things you can represent. 2^0=1 thing you can represent (just that one thing, no options, no either/or). A byte is a collection of 8 bits, giving us 2^8=2x2x2x2x2x2x2x2=256 possible things you can represent with one byte.

Unless I mention otherwise, I'm going to talk about bits and bytes from here on out in terms of binary numbers. One bit can represent the numbers 0b0 and 0b1. Whenever I talk about binary numbers I'll start it off with "0b" first (that's a zero followed by the letter 'b'). If I omit the "0b," then I'm talking about regular decimal numbers that we're all so used to. The 'b' in "0b" stands for "binary," so that's an easy way to remember that. I am always going to use binary numbers to represent bit strings. A bit string is just a series of bits of any length. A byte is a bit string of length 8.

Here are two example bit strings for two different bytes: 0b1010 1010 and 0b1111 1111 (I added a space every 4 digits just for readability's sake, and remember, the "0b" at the beginning just means it's in binary). We can consider these as binary numbers, with each bit representing a digit in the binary number system, and when we look at all the bits together we can determine the value of the number. Or, like I mentioned last time, we can give arbitrary meaning to each of those bits and treat them as separate entities (not part of a larger binary number) that each tell us something about the computer, like which physical switches are turned on or which lights are blinking. The human designing the system gets to decide how all of the bytes in the system will be used.

If a byte is a collection of 8 bits, and represents a binary number, then its low value would be 0b0000 0000, and its high value would be 0b1111 1111. 0b0000 0000 is the same as the decimal number 0, and 0b1111 1111 is the same as the decimal number 255. So a single byte can represent numbers in the range of 0-255, or in other words it can represent 256 distinct numbers (0 counts as a number).

Back in the day when we only had 8-bit computers, mathematical operations could only be done directly on numbers of single-byte size, so only on values ranging from 0-255. In order to represent larger numbers and do mathematical operations on larger numbers, programmers had to cleverly build those larger operations out of multiple uses of smaller operations. As 16-, 32-, and 64-bit computers were developed then we no longer had to use those tricks to perform math on large numbers because the computer now has hardware to do those operations directly. A modern 64-bit computer can represent integers in the range of 0-18,446,744,073,709,551,615, so you only have to use those tricks from former years if you want to use numbers larger than that.

Next time we'll look at how to do basic arithmetic on binary numbers, how it's different from arithmetic on decimal numbers, and especially how it's exactly the same.

Of bits

People have heard the terms "bits" and "bytes." Many people even know that computers have 8 bits to a byte. But what is a bit, and why do bytes have 8 of them? "A bit stores either 0 or 1!" That's a pretty good answer, but I think that doesn't tell the whole story.

We'll consider later how bits are stored in a computer and how computers use them, but for now let's just talk about the mathiness of bits. A bit is a "thing" that can be in either of two states. It doesn't really matter what the "thing" that a bit takes the physical form of, and it doesn't matter what the two states are. For example, and bit could be an electrical switch, and when it is turned in one position that means "1", and when it's turned in the other position that means "0." That's probably an example you were expecting if you already knew about bits, but that's just one of many possibilities. How about a glass of water that when it's full it represents "elephant," and when it's empty it represents "pocket knife?" That's another example of a bit (assuming that the glass can only either be full or empty, of course).

The point is that a bit is a "thing with two options." It can either be one way or it can be the other way, but it must be one of those two ways. It cannot be both at the same time, and it cannot be neither. A bit only has the meaning a person gives it. In computers, a bit is most often used in one of a few ways. It can denote a single digit in the binary number system (0 or 1), it can represent "true" or "false" in logic formulas. Also, if the computer is connected to any physical switches, the way a switch is flipped will be represented in the computer as a single bit. In all of those cases, it's up to the human in charge of the computer to decide what the two states of a bit really mean, or in other words, how they're going to use the information they gain by examining the state of the bit, and what it would mean to change that state.

Next time we'll look at how sets of multiple bits can work together to represent a greater variety of things than a single bit can by itself.

The first one

Hi. My name is Seth and I study computers. I really like computers. Sometimes I claim to hate computers. Maybe there's a bit of both going on. Anyway, I wish more people knew about computers and how they work. Hopefully I can share a bit of what I know with you. I'm going to start with things that I consider basic, and move on from there. I don't want any one post to be too long or heavy, so I'm going to try to keep things concise and simple, and break important concepts into multiple, bite-sized posts if I need to. If I ever use any big words, let me know and I'll correct it. Big words should almost never be used by anyone at any time.

Also, if you think I'm wrong about something, let me know in the comments. If I agree that I'm wrong and I feel like fixing it, I will. However, I might be intentionally wrong. I'm trying to explain computer science with as little required background as possible, so I might simplify things and gloss over details that are a big deal in real life, but aren't important for these discussions.