In this lecture, we'll talk about how we can encode things in a computer using bit and we'll also talk about how many bits do we need to encode a particular number of unique things. Everything in the computer is in binary. What's binary? Binary is base two. Why do we care about that? Because we can use 1s and 0s to represent anything in a computer. We can represent numbers, we can represent characters, we can represent pictures, we can represent sound, we can represent anything with 0s and 1s. That raises the question though, first, how do we do it, and second, how many bits do we need to represent a particular number of things? That requires me to tell you a Christmas story. My family several years ago, we're trying to figure out who gets to open the first present. That's part of our tradition of Christmas and we wanted to do it with coin flips. We were thinking about how many coin flips did we have to do to pick out of four people, one of my children was not there yet. Out of four people, how many coin flips did we have to do to figure out who open the first present? Now, me and my son, a computer scientist, came up with one answer and my wife and daughter came up with a different answer. You should pause the video for a minute and think about how many coin flips you would need to do to actually pick from four people, the person who gets to open the first present. Once you've figured that out, go ahead and unpause the video and I'll talk through the two different solutions that we came up with that Christmas morning. One of the common solutions that we might use would be to have a tournament. This is a standard structure that you see in playoffs in hockey or some other inferior sport to hockey. You have these ladders, if you will, and you have A plays B and somebody wins, and that would be one coin flip. C plays D and somebody wins and that would be another coin flip. Finally, the winner of those first two games, if you will, play with one more coin flip. You can do that with three coin flips. That's a very natural normal way to come up with a solution to this problem. However, I'm going to be very dramatic here. We can use the power of binary and we can actually encode A, B, C, and D, each of those four different things by using 2-bit. If we encode A as 00 and B as 01 and so on, we can actually determine who wins with only two coin flips. I will freely admit that we spend far more time talking about this than it would have taken to do a third coin flip. But that's how my family works. But the next question is, how many bits do we need to represent a certain number of unique things? This was a really interesting conversation because it was, how we go about encoding stuff in the computer. But if we're going to encode stuff, how many bits do we need to encode stuff? Let's say we have 1-bit. We can encode two unique values. We can have zero or we can have one, two unique values. What if you have 2-bits? Well, that was the example we just did, we can encode for different things. If we have 3-bit, we have eight different possible encodings; 000,001, 010, 011, 100, 101, 110, and 111. Let me fix my glasses. I was counting up in binary. But those are the eight different combinations we can get with 3-bit. Now some of you may have already realized that, if we have 1-bit, we can represent two things and two to the power of one is two. If we have 2-bits, we can represent four things, and two to the power of two is four. If we have 3-bits, we can represent eight things and two to the power of three is eight. Now I'll show you a slide with the biggest font you'll see throughout the course. The relationship is two to the b equal n. If we know how many bits we have, we just raise two to the power of b and that tells us how many unique combinations of those bits we get, which tells us how many unique things we can represent. If you know how many things you want to represent, you can use the inverse relationship. We can take the log base two of n to calculate b. But I'll tell you, I personally never do that. I go through the process. Well, I'm trying to represent 12 things. How do I figure that out? Is 3-bits enough? No, two to the third is eight, is 4-bits enough? Sure, two to the fourth is 16. We can never use partial bits. You can't say I need 3.7 bits, it's not how it works. You only get a whole bit. But I don't usually use the log base two n equation. I usually use two to the b equal n and work my way into however many bits I need. That's it for this lecture. The two powerful ideas are, we can encode anything with 0s and 1s in a computer and we have to because computers use binary and we have this relationship, this two to the b equal n, that will tell us how many bits do we need to encode n unique things.