Welcome to Exploring Computing.
Today's video is Bits, Bytes, And Binary, part 2, or 1 plus 1
equals 1 0?
So in the last lecture, we took a look at binary numbers
and why computers use the binary number system.
In this lecture, we're going to take a close look at how
binary numbers actually work.
Now, I do want to start off by saying,
we are going to be taking a look at a bit of math
here in this particular video.
And I don't want people to think that this
is what the bulk of this class is going to look like.
This is largely the only video in which we're
going to be looking at math.
But I do think that having a sense of how
these binary numbers really work and getting a sense for when
you see a binary number, what it actually might represent
is going to be pretty useful as things go on.
We're going to see that the binary number system pervades
computers and that there are many, many places where
the fact that the underlying representation of data
in the computer uses these binary numbers
is going to leak out into the real world.
Let's go ahead and take a look at this.
So let's start off by learning how to count.
Now, I know that seems like an odd place
to start off a lecture at Stanford University,
but bear with me.
We're going to review how to count in decimal.
And this will turn out to be useful
when we're trying to understand how counting in binary works.
So I'm going to start off with a 0,
and I'm going to add 1 to it.
And of course, that's going to give us one.
We're going to add 1 to 1, and that will give us 2.
We'll add 2 to 1, and that'll give us 3 and so on.
And then, we'll continue on.
We'll get to 8.
We'll add 1 to 8.
That'll give us 9.
We'll add 1 to 9, and that's where things get a little bit
dicey because, remember, we're working with the decimal number
system.
There are only 10 digits, starting with 0 going up to 9.
And so what happens when we try and add 1 to 9
is there's no 11th digit.
So what happens is we carry the 1, and we reset our 1's to 0.
And we end up with 1 0, which is, of course, 10.
Then we can continue on.
So 10 plus 1 is 11, 11 plus 1 is 12, and so on.
Now when we get to 19 plus 1, well, this
is similar to what happened with the 9 plus 1.
We know that we can't go to 1 some digit greater than 9
because there are only 10 digits, 0 through 9.
And so again, we carry the 1 over, and we end up with 20.
This will continue on.
We get 98 plus 1 equals 99.
We get 99 plus 1.
And again, we have this situation
where neither the tens digits nor the ones digit
can go any higher.
We only have 10 digits, so we carry over
from the ones to the tens and from the tens to the next digit
over, which will be the hundreds.
And so we end up with 100.
Fair enough.
Let's take a look at how this works in binary now.
So in binary, we're going to start off with 0 plus 1
again just as we did in decimal.
0 plus 1 in binary is equal to 1 just as 0 plus 1 in decimal
is equal to 1.
But as soon as we get to the next step,
we run into a problem.
What does 1 plus 1 equal in binary?
Well, this is analogous to the situation
we got to before when we tried to add 1 to 9
in the decimal number system.
In the decimal number system, we had those 10 individual digits.
In the binary number system, we only have two digits, 0 and 1.
So when we add 1 to 1, there is no third digit.
There's only 0 and 1.
And so we need to go ahead and carry the 1 over.
So this will actually give us 1 0.
We can go ahead and add 1 to 1 0, which will give us 1 1.
When we try and add 1 to 1 1, this
is similar to the situation where we try to add 1 to 99.
We need to carry the 1 over, and so we're going to get 1 0 0.
We can keep on going with this.
So 1 0 0 plus 1 equals 101.
We can keep going and continue on.
And so, what I've written up here
is the first eight numbers of the binary number system,
or actually the first nine if you consider 0
as the first number in the binary number system.
So 0, 1, 1 0, 1 1, 1 0 0, 1 0 1, 1 1 0, 1 1 1,
and, finally, 1 0 0 0.
So here are the first 16 numbers in the binary number system.
And you can see that they are the equivalent
of the decimal numbers 0 through 15.
You'll also notice that I've got these little subscripts
next to each of the numbers.
So these subscripts are sometimes
used to disambiguate when it's not clear
what particular number system a number is using.
So in this example here, I've got the number 6 on the left.
But I want to emphasize that it's a decimal number so
that 10 in subscript after the six
represents that 6 on the left side here is base 10.
And the 2 on the--
that the subscript on the right represents that number
on the right is base 2.
Now without that subscript 10 and without that subscript 2,
you would probably guess that the number on the left
is base 10 because it's clearly non-binary.
It's got a digit there 6, which does not exist
in the binary number system.
Although, there are some other number systems like the base 8
number system, which occasionally gets
used in computer science.
And then there's a base 16 number system
called hexadecimal, which does get used quite a bit
in computer science.
We'll look at that in another lecture.
And so that 6 on the left could be either one of those number
systems.
And so putting that 10 down there at the bottom
emphasizes that this is, in fact, a decimal number.
And on the right, 1 1 0, this could represent 110 in base 10.
And so that little subscript there 2 tells us
that, no, this is not 110, this is actually
1 1 0, which does kind of bring us to the next question, which
is, how are we working out the equivalencies
of these different numbers?
So let's take a very short look at this.
And I'm not going to require you guys to be
able to do the conversion from binary
to decimal at any point in the quarter.
And this is the point where I would normally
say we're not going to make you do it on an exam.
But, hey, because we're under quarantine there are no exams,
so go coronavirus, I guess.
But I do want you to have a sense of how it works.
So again, we're going to start with a decimal number
because this is a system we're used to.
And by reminding ourselves of how the system actually works
will help us when we try and convert it to binary.
So here I've got the number 1891.
Now if you think about what does 1891 actually represent,
we've got four different digits here.
The one on the far right represents 10
to the zeroth power, which is our ones.
The second number over, the 9, represents
our 2 to the first power, or our tens.
The 8 represents 10 to the second power, or hundreds.
And the fourth number over represents our third powers,
our 10 to the third, which is a thousand.
So if I'm looking at 1891, I know
I have one 10 to the zeroth power, I have nine 10
to the first powers, eight 10 to the second powers, and one 10
to the third power.
So I have 1 plus 90 plus 800 plus 1,000,
which gives us 1891.
Let's go ahead and take a look at how
this works with binary numbers.
So, here I've got the binary number 1 1 0 1.
What is the decimal equivalent of this?
Well, on the far right in the zeros place,
I have my 2 to the 0.
So these are 1 because 2 to the 0 power is 1.
The next place over represents my 2 to the first power,
so those represent our 2's.
Next to that to the left, I have our 2 to the second power,
which represent 4's.
And then one step over from that,
I have our 2 to the third powers, which are 8's.
In this particular case, I have one 2 to the zeroth power.
I have no 2 to the first powers.
I have one 2 the second power.
And I have one 2 to the third power.
So I have 1 plus 0 plus 4 plus 8,
which means that this is the equivalent of a decimal 13.
So one thing that's going to be important for us
when we're representing information
is, how many different combinations can we store
in a given number of bits?
So let's start off with 1 bit.
What can we represent in a single bit?
Well, we can either represent a 0 or a 1.
What is that actually good for?
The most common thing that we can use a 0 or a 1 to represent
is actually whether something is true or false.
So are we going to be able to come back
to Stanford for summer session?
Well, if that bit is starting at 1, then the answer is yes.
And if that bit is starting at 0, then the answer's no.
How many different combinations can we store in 2 bits?
Well, here are the different combinations of 2 bits,
and you can see that there are four possible combinations.
How about the combinations in 3 bits?
Here are the different combinations in 3 bits.
And then finally, here are the combinations of 4 bits.
So the way to think of these is, you can either
think of them as, oh, those are binary numbers,
and we saw how to convert those to decimal a minute ago.
So we have these 16 possible combinations.
These could represent the decimal numbers
between 0 and 15, but they might be used
to represent something else.
So for example, I could use these 16 combinations
to represent the 10 provinces in Canada.
So if we were a school in Canada and we wanted to know which
province somebody lived in, I could have 0000, for example,
represent Prince Edward Island, and 0001 representing Nova
Scotia and 0010 representing New Brunswick and so on.
Could we represent information about US states in our 4 bit?
No, we can't.
There's 50 different states, and we can only
store up to 16 different combinations in our 4 bit.
So, while our Canadian provinces fit in the 4 bit,
and, in fact, we could comfortably
add in the three Canadian territories as well,
we simply do not have enough space in 4 bits
to store the US states.
And in fact, if we had 5 bits, we still couldn't store.
We're going to see that we actually need 6 bits to store
all the states of the Union.
So we've seen that in 1 bit, we can represent two combinations.
In 2 bits, we can represent 4, 3, 8, 4, 16.
And it turns out there's a simple formula here.
If we have n bits, we can represent 2
to the n combinations.
And so here you can see the number
of combinations we can have for 1, 2, 3, 4, 5, 6, 7, 8, 9
and 10 bits.
Now, when you're looking at these different combinations,
keep in mind that these individual bits
could represent numbers.
They can represent positive and negative numbers.
They can represent different things
like our Canadian provinces.
We could use a certain sequence of bits
to represent dorms at Stanford.
And so, one of the things that the programmers are going
to have to decide to do is what do they want
to do with the individual bits.
When we're designing a program, we're
going to need to decide how many bits to set aside
for what particular quantities and how
we're going to represent things with bits and bytes.
And that's something that we're going
to be exploring more later this lecture
and throughout the rest of this week.
Now another thing that you might notice
is if we're looking at these numbers here,
2, 4, 8, 16, 32, 64, 128, 256, 512, these
may look a little bit familiar to you.
If you've gone shopping for a new say iPhone recently,
how much memory do you buy on an iPhone?
Can you buy 100 megabytes?
Can you buy 250 megabytes.
No, you buy 128 or 256 or 512.
Why?
Because those are powers of 2 and because internally
the computer uses the binary number system.
Now we've only solved half the mystery, though.
Now we understand why we buy iPhones with 64 or 128 or 256.
But why do we buy them in megabytes or gigabytes instead
of millions and billions?
Well, it turns out that millions, billions, thousands,
these are all powers of 10.
And again, internally, we're using the binary number system
not the decimal number system.
And so kilobytes, megabytes, gigabytes, and terabytes
are the base 2 equivalent.
And you can see from this table here that 2 to the 10th
is about 1,000, but it's actually a little bit bigger.
And 2 to the 20th, which is a megabyte is about a million,
but it's actually a little bit bigger.
And the same thing for gigabytes and terabytes.
So the idea here is we're going to give you
roughly the same amount as a billion
or a million or thousand, but we want to do it in a power of 2.
And you can see here are some higher order numbers
that you might run into some day-- peta, exa, zetta,
and yotta.
I should mention that there is some disagreement
between the electrical engineers and the computer scientists
on whether or not we should be using powers of 2.
So there are places where, when we're
working with electrical engineers,
they will use kilo, mega, or giga,
and they'll actually be referring
to thousands, millions, and billions in base 10.
And so the most common place you might run into this
is when you're talking about communication speeds.
Those are generally actually given in powers of 10.
In the next section, we're going to take a look
at what happens when things go wrong with our binary numbers.