CS 100 (Learn) — CS 100 (Web) — Module 01
NOTE: If your internet access is restricted and you do not have access to YouTube, we have provided alternate video links.
In this video, we are going to re-learn how to count.
But first, a tiny bit of notation.
A number, like five nine seven eight [5978], is made up of digits. We are going use the notation that each digit is in a different column. To keep track of the different columns, we are going to number them.
In computer science, we always start counting from zero. The day that you were born was your "zero-th" birthday.
We are also going to start on the right, so the rightmost column will be column zero, the next column to the left will be column one, and so on.
So for the number five nine seven eight [5978], the digit five is in column three, the digit nine is in column two, the digit seven is in column one, and the digit eight is in column zero.
Also, there are always "hidden" leading zeros in front of any number. The number five nine seven eight [5978] is the same as the number zero zero five nine seven eight [005978]. The number seven is also zero zero seven.
So if I were to look at the number five nine seven eight [5978] and ask, what is the digit in column five, the answer would be zero.
So let's start counting. Remember, in computer science, we always start with zero.
To get to the next number, we add one the digit that is in column zero. We will continue to add one to the digit in that column until we run out of digits:
zero, one, two, three, four, five, six, seven, eight, nine... [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
We've reached nine, and now we're out of digits. So now what? We reset the digit back to zero, and then add one to the digit in column one.
ten [10]
Great, now we go back to what we were doing before and keep incrementing column zero.
one one, one two, one three, one four, one five, one six, one seven, one eight, one nine ... [11, 12, 13, 14, 15, 16, 17, 18, 19]
And now we're out of digits again, so we reset column zero and add one to the digit in column one.
two zero, two one, two two, dot dot dot, two eight, two nine... [20, 21, 22, ... 28, 29]
So the rule we are following is: try to add one to the current column. If we can't because we're out of digits, then reset the current column to zero and move one column to the left and try again.
So we're on the number two nine [29].
We start at column zero, but we can't go past digit nine. So we reset the current column to digit zero, and then move one column to the left and try again. That digit is two, and we can add one to that digit to become three, and then we are done.
three zero [30]
Let's try our rule when we are on the number nine nine [99].
We start at column zero. We are at digit nine, so we reset the current column to zero and then move one column to the left. We are now in column one, but that digit is also the digit nine, so we reset the current column to zero and move one column to the left. That digit is zero, so we add one to that digit to become one, and we're all good.
one zero zero [100]
So let's generalize how to count:
This has all been a bit tedious and pedantic, but now we are going to add a twist.
The only reason that we use ten digits (zero through nine) is because we have ten fingers. There is really no other good reason that we use ten digits.
The number of digits that you use is known as the "base" of the system, so we use a "base ten" system. It's also called the decimal system because the deci- means ten.
If we lived in the Simpson's universe, where people have four fingers on each hand, we would be using "base eight", or an octal system. True fact: some of the Simpson's writers have PhD's in Mathematics so they sneak in base eight and other math jokes into the show.
Let's see how Homer would count. Actually, that's not a good idea. Let's see how Lisa would count. First, Lisa would only have eight digits: zero through seven.
So she would count the same as us:
zero, one, two, three, four, five, six, seven... [0, 1, 2, 3, 4, 5, 6, 7]
Remember our rules for how to count. She has already run out of digits, so the next number would be one zero. So it would go:
six, seven, one zero, one one, one two, one three, one four, one five, one six, one seven, two zero, two one, two two... [6, 7, 10, 11, 12, 13, 14, 15, 16, 17, 20, 21, 22]
That might seem really weird and awkward to you, but that would be perfectly natural for her.
What if we had base four?
zero, one, two, three, one zero, one one, one two, one three, two zero, two one, two two, two three, three zero, three one, three two, three three, one zero zero, one zero one, one zero two, one zero three, one one zero... [ 0, 1, 2, 3, 10, 11, 12, 13, 20, 21, 22, 23, 30, 31, 32, 33, 100, 101, 102, 103, 110]
And, of course, our real interest is in how computers count in binary, which is base two...
zero, one, one zero, one one, one zero zero, one zero one, one one zero, one one one, one zero zero zero, one zero zero one, one zero one zero... [0, 1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010]
If we lived in some bizarre Cthulhu-like universe where we had octopuses for hands we would use base sixteen.
Now, we only know ten digits (zero through nine) but they would have six more digits. It's hard for us to imagine digits that don't exist for us. We could make up new symbols, but instead we just use the letters A through F for those six digits:
zero, one, two, three, four, five, six, seven, eight, nine, A, B, C, D, E, F, one zero, one one, one two... [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F, 10, 11, 12]
If you can believe it, the ancient Babylonians used a system that was essentially base sixty, but they didn't have a good grasp on zero yet, so it was a little messy.
If you follow the basic rules for counting that we established, it will work for any base greater than or equal to two.