Loose ends: binary

I said in the talk that binary did not need digits larger than one, because you could write the digit two simply by taking a one and shifting it left once. This works because wherever in the number that digit two might be, the digit to the left of it will always count twice as much.

Let's take the number 12 as an example. Note that this isn't the number twelve – it's still in binary, so the shift factor is still two, so the one in the first place only counts for two. Together with the two in the last place, that makes four, so let's see what the proper way for writing four in binary is.

As I have said, in binary, a one in the second-to-last place is worth exactly as much as a two in the last place. We can therefore take the two away and add another one to the second-to-last place, like so:

                1 2
                | |
                | 2
               / /
               |1 0
               ||
               \|
                2 0
            

So 12, in binary, is the same as 20, in binary. But we've still got a two as a digit! Let's shift again:

                2 0
               /  |
              1 0 0
            

So this is also the same as 100, in binary. And now there's no more twos, so we're done – four, in binary, is 100.

The simpler way to see that this is true is to start with 1, and then shift it to the left twice. Each time, it gets multiplied by two: 100 = 10 · 2 = 1 · 2 · 2 = 4.

But what about three, as a digit? Well, we can do the same thing, except that this time, a one gets left behind in the last place, since 3 – 2 = 1:

                  3
                 /|
                1 1
            

Now, just for completeness, we could do the same piecewise approach for four: Take two away from the last position, and add one to the second-last.

                  4
                 /|
                1 2
            

We arrive at 12, and proceed as above. However, there's an easier way. Since the digit to the left is worth twice as much, we can also just divide the four by two while moving it left. Do this twice, and we arrive at the result from above:

                  4
                 /|
                2 0
               /| |
              1 0 0
            

This trick works for five too. Again, five can't be divided by two, but if we leave a one behind, we're left with four, which can. And you've already seen how four works.

                  5
                 /|
                2 1
               /| |
              1 0 1
            

Let's see how all of this works for nine. It's not divisible by two, but if we leave a one behind, we get eight, which is. So the eight shifts into a four, which shifts into a two, which shifts into a one.

                  9
                 /|
                4 1
               /| |
              2 0 1
             /| | |
            1 0 0 1
            

So we arrive at 1001, and perhaps you can see that there's a very simple process behind this: if the number is not divisible by two, we subtract a one and leave it behind. The rest we can divide by two as we shift it left once. If a number is already divisible, we only shift and divide, leaving behind a zero.

If you're careful enough, you can do this with every number – not just ones that fit into a single decimal digit. Let's take the number twenty-five (as in, two tens plus a five) and see if we can keep everything straight. Conceptually, this entire number is now sitting in the last place of our future binary number, even if that's a bit hard to write.

Either way, we can do as we have before. Twenty-five can't be divided by two, so we leave behind a one and get to twenty-four, which halves into twelve as we shift it to the left. (The two tens halve into one ten, and the four halves into a two. Together, these make twelve.) The twelve halves cleanly into six, leaving behind a zero. The six halves again into three, leaving behind another zero. Three isn't divisible nicely, so we leave behind a one and watch the remaining to halve into a one.

Lets look at the digits we've left behind, remembering to arrange them from right to left since that's the direction we've been moving in: 11001 – that's twenty-five in binary.