Sunday, October 26, 2014

Binary

Before, I talked about some of the things computers can do using only two values. But what about numbers? How can computers do arithmetic with only 0s and 1s? The answer to that question is "binary". If you already know what binary is, this post will just be a refresher.

Before I begin explaining binary, let's go over how the number system we normally use, that is, base ten, works. How do you count? How do you determine what the next number is?

Well, you start with 0, which is followed by 1, then 2, 3, 4, 5, 6, 7, 8 and 9. You pretty much just have to memorize that sequence. But what comes after 9? 10. That's interesting. It's not just another symbol, it's two symbols, and two symbols we've seen before.

Let's continue. After 10 comes 11, 12, 13, 14, 15, 16, 17, 18, 19. Hey, that looks familiar. Those numbers are the same as the first ten, except with a 1 on the front of each of them. And what comes after 19? 20. And the same sequence as before will repeat again, except with a 2 on the front, instead of a 1. And after that comes 30. And then, the same sequence will repeat again, but with a 3 this time.

Hey, wait a minute. The number on the front is itself going through that sequence too, it's just waiting for the second number to cycle through before going to the next step. So, after 30 comes 40, then 50, 60, 70, 80, 90.

So, what comes after 99? 100. Another symbol got added, just like when 9 turned into 10. And that's all there is to counting. You can continue following these same steps forever, and you'll never run out of numbers. Let's write out these steps a little more explicitly.

First, you have to memorize a sequence of symbols: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9].
Then, to get the next number after the current one, replace the rightmost digit with the next symbol in the sequence. If it's already at the last symbol, then set it back to the beginning of the sequence, and repeat the last step for the next digit to the left. If there is no digit to the left, it's implied to be 0, so 1 is added.

But notice, there's nothing special about that sequence of symbols. You could follow the same rules using any sequence of symbols. For example, you could use this sequence: [a, b, c, d]. Then you would count a, b, c, d, ba, bb, bc, bd, ca, cb, cc, cd, da, db, dc, dd, baa...

Or you could use this sequence: [0, 1]. Then you would count 0, 1, 10, 11, 100, 101, 110, 111, 1000...

And that's what binary is. Counting, with only 0 and 1.

What if you want to convert from one base to another? If you have a number in base ten, and want to know how it's written in binary, or the other way around?

Well, one way to do that is just to count. Numbers are the same, regardless of how they're written, so if you count up the same number, it will be the same in every base.

Base ten0123456789101112
Binary01101110010111011110001001101010111100

But that's going to be cumbersome for large numbers. Is there an easier way?

Yes, there is. Notice, that in any base, the number 10 represents the number of symbols in the sequence you're using. There are ten symbols in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], and 10 represents ten. There are two symbols in [0, 1] and 10 in binary represents two. That's not a coincidence, and I trust you're smart enough to figure out why that is.

A consequence of that is that the number 100 in any base is going to be equal to the number of symbols times itself. 10*10 = 100. And this gives you the concept of "place". You know, the digit furthest to the right is the ones place, the next digit to the left is the tens place, the next digit to the left is the hundreds place and so on.

That concept applies to any base. The rightmost digit will always be the ones place. The digit there stands for itself. The next digit to the left will be multiplied by the base. Each further digit to the left will be multiplied by the base again. So in binary, you get the ones place, the twos place, the fours place, the eights place, and so on.

So, for example, let's try that on this binary number: 101011
The rightmost digit is 1, and it's in the ones place, so it's equal to 1.
The next digit is 1, and it's in the twos place so it's 1*2 = 2.
The next digit is in the fours place, but it's 0, and 0 times anything is still 0, so it's 0.
The next digit is 1, and it's in the eights place, so it's 8.
The next digit is in the sixteens place, but it's 0.
The next digit is in the thirty-twos place, so it's 32.
So, the value is 32 + 8 + 2 + 1 = 43.

What about the other way? Converting a number from base ten to binary? That's a little bit harder to describe, so I'll explain with an example. Say we're converting the number 57. What we need to do is divide that number by 2 and find the remainder. 57 / 2 = 28 remainder 1. The remainder is the rightmost digit of our binary number.
To continue we need to divide 28. 28 / 2 = 14 remainder 0. The next digit in our binary number is 0.
14 / 2 = 7 remainder 0.
7 / 2 = 3 remainder 1.
3 / 2 = 1 remainder 1.
1 / 2 = 0 remainder 1.
So our binary number is 111001.

In other words, in each step you need to divide your number by two. The remainder is the next digit of the binary number, starting from the right and going left. You're done when the result of the division is zero.

And that is how you can represent numbers, using only 0 and 1.