All you need is just one bit

One bit of information. In the age of terabytes and gigaflops one bit sounds like nothing.

Well, I'm here to remind you not to underestimate the power of a bit.

One bit of information. What does it even mean? If you go to your very first computer science class or open your very first computer science book you'll probably learn that a bit can be either 1 or 0. Or "true" or "false". This is dry and boring. Also that kind of explanation makes the bit looks small. Let's try something else.

One bit of information is a choice. A choice between two things. Which things? Well, depends on what kind of information we are interested in. For example, we might be interested if the cat in that box over there by the fridge is alive or dead (yep, people still want to know what's in the box). Or we might be interested in whether we're going to get promoted or fired (sorry, too soon?). Or we might be interested in knowing... who killed the last leprechaun.

Adventure time!

Grab a cup of your favorite comfy beverage and let's go into the imaginary land of WTF-is-happening-and-how-did-we-get-here...

The last leprechaun is dead. It's obviously a murder cause leprechauns don't just die of old age or clumsy accidents. We have eight suspects. And in this land we, as detectives, are only allowed to ask three questions. If we reach the limit of questions and still don't know the answer the infamous they are going to take our heads and make kids toys out of them!

Sounds fun and stupidly dangerous. Eight choices, three guesses? No worries, my dear Watson.

The suspects:

1. guy; beard; mustaches; hat; jacket

2. guy; beard; mustaches; no hat; jacket?

3. guy; beard; no mustaches; hat; no jacket

4. lady; no beard; no mustaches; hat; no jacket

5. guy; no beard; mustaches; hat; jacket

6. guy; no beard; no mustached; hat; jacket

7. guy; no beard; no mustaches; no hat; jacket

8. guy; beard; mustaches; hat; no jacket?

(I have just generated a random number from 1 to 8 to make. This will be the killer we need to find.)

Now, we need to be smart and try to get as much information as possible with each question.

The more information we can get the more we can minimize the list of suspects and the easier it will be to find the killer.

At this moment we might ask if the killer is a man or a woman. But there's only one woman in the list so if the killer is a man we will only minimize the list of suspects by one. Meaning, we didn't really get a lot of information. Looking at the list we already know that the killer is probably a guy.

There's also a question of hat. We have six suspects with a hat. This question will split the list 4 to 6. Not bad. But maybe we can do even better.

There are four suspects with beards and four without. We can halve the list! Let's do it!

Q: Does the killer have a beard?

A: Yes

All the beardless people are free to go! Let's also remove "beard" from the descriptions. They all have one so it's not important anymore. It also seems that they are all guys, so we don't need to worry about that part anymore.

So far the killer is a guy with a beard...

1. mustaches; hat; jacket

2. mustaches; no hat; jacket?

3. no mustaches; hat; no jacket

8. mustaches; hat; no jacket?

What now? Well mustaches and hats give us 3 to 1 split. Considering that we have only two questions left we cannot have a list of three suspects, cause then it will all come down to a lucky guess. Or an unlucky guess. We don't want to play chances with our lives, right? Right?!

Seems that half of them are wearing a jacket though...

Q: Does the killer have a jacket?

A: No

OK, don't care about jackets no more.

3. no mustaches; hat

8. mustaches; hat

We have one question, two answers and only one of the suspects have mustaches. Easy!

Q: Does the killer have mustaches?

A: No

3. no mustaches; hat;

Suspect number 3 is the killer. Why did you do it, number 3? Was it for the money? The power? Was it to explain information theory to some strangers? Anyway your punishment is... We obviously need a new leprechaun, so... suit up!

But... but... what does a bit has to do with any of this?

OK, I might have gotten carried away just a tiny bit with the example. Please note that with only one bit we were able to get enough information to minimize the list of suspects in half. Half! Instead of investigating every person from the list of eight we could think of three questions that gave us the killer with no extra grunt work.

Remember, each bit represents a choice. Or we can think of it as an answer to one question. No matter how big the question is if it has only two answers we can represent it as one tiny bit.

In our example we had to ask three questions, which means three bits. Three bits to code the whole investigation of eight suspects. Three bits. That's small. And that's the super power of a bit. It looks unassuming and weak. It's so simple. It takes very little space in our computers' memory or even in our own memory. But it can hide a lot of information behind it.

I'm not going to bore you with math and big numbers. But if you're not impressed yet ask yourself (and your calculator) how many suspects can I process if I have only 10 questions. How about 20 questions?