Thursday, October 18, 2007

Powers of two

Several years ago, when memory sizes were measured in Kilobytes and hard drive capacity in Megabytes, I came up with this trick for knowing the powers of two.

As an aside, my first personal computer (an Apple ][, acquired in 1979) came with 4K bytes of memory and no disk drive at all (a cassette tape interface was all there was for storage). I spent a couple of hundred dollars to upgrade the memory to 16K bytes. My first IBM-compatible PC (1988) had 256K (bytes) of memory and a 20Mbyte hard drive. How times have changed!

The (Intel) processor in an IBM PC could only use 16 bits to form a memory address. It turns out that this is enough capacity for there to be a unique address for each of 64 Kilobytes (about 64 thousand bytes).

Each bit can have only one of two possible values, typically written as zero or one. Here is a little table showing how many different bit combinations there are for different numbers of bits:

1 bit gives you two possible values (0 and 1)
2 bits give you four possible values (00, 01, 11 and 10)
3 bits give you eight possible values (000, 001, 011, 010, 110, 111, 101 and 100)
and so on

In each case, I have been able to show all of the possible bit patterns. But the number of possible bit patterns doubles each time we add on an additional bit. The numbers get big quite quickly, and it would soon become very tedious to write out all of the possible bit patterns.

Mathematicians would express this relationship--number of bits and the number of possible bit patterns--using powers of two. The sidebar shows a chart from 0 bits through 9 bits.

You'll recognize three of these lines from the earlier table (showing 2, 4 and 8 possible values, for 1, 2 and 3 bits, respectively).

Above those lines, there is a bit of an oddity for zero bits, allowing only one pattern.

Now, if you want to learn my little memory trick, you will have to memorize these ten lines. This effort will be well repaid, as this will allow you to mentally state memory or disk sizes from the smallest to the largest in use today.

Where things get interesting is at 10 bits, which allow us to produce 1024 possible bit patterns.

What is interesting about this is that 1024 is the number commonly known as "Kilo". And, this is really quite close to one thousand.

Now, the power of 2, as represented by the exponent--the number shown attached to the upper right hand corner of the 2--can be interpreted as the number of bits that we have available for producing possible bit patterns. The other number--after the equals sign--is the number of possible bit patterns.

If you've studied powers and exponents, you'll know that you can add exponents (on the left) by multiplying numbers on the right of the equal sign. So, for example 2 to the 16 will be equal to 1024 (2 to the power 10) times 64 (2 to the power 6). This yields the number 65536, but which is more commonly expressed as 64K.

This is just another way of saying that 16 bits allow us to have a distinct address (bit pattern) for each of 64 Kilobytes. This is approximately 64 thousand bit patterns, because 2 to the power 10 is approximately one thousand. Similar approximations hold for 2 raised to 20, 30, 40, etc.

As it happens, 10 bits allow us about a thousand possible bit patterns, 20 bits allow about a million possible bit patterns, 30 bits allow about a billion possible bit patterns, and so on.

Now we are ready for the trick. When you have some number of bits (between none and 69), you can combine what you know from these two figures.

Let's try a few examples. If you have 24 bits, that would be about 16 million possible bit patterns. The "16" comes from the first figure, where 2 raised to 4 gives us 16. The "million" comes from the second table where 2 raised to 20 gives us about a million. Of course, 24 is just 4+20, so the law of exponents will be satisfied. This is also written "16M" or "16 megs" or "16 megabytes".

If you have 32 bits, that would be about 4 billion possible bit patterns. This is also written 4G, or "4 gigs" or "4 gigabytes".

Now, what if you have 64 bits? Would that be twice as many possible bit patterns as 32 bits? No, 64 bits would be about 16 thousand quadrillion possible bit patterns.

It works the other way, too. How many bits would you need for twice as many bit patterns as you get from 32 bits? Well, 32 bits gives us about 4 billion patterns, so we need about 8 billion bit patterns. Using the two figures, we can see that it will take 33 bits to give us about 8 billion bit patterns.

Did anyone actually get this far? Hope you find this useful.

4 comments:

Nancy said...

Josie has been working on exponents recently. I'll have to have her read this.

My hard drive is 20 GB. I only have 4 GB free, and that's because I completely fill up my hard drive every other week, it seems.

I move stuff to our 240 GB external hard drive that is already half full.

It doesn't help that I have multiple hundred page books waiting to be finished and well over 5000 pictures (with hundreds more added weekly).

I need to stop taking so many pictures of Rachel...I don't think I ever could have survived with only 16 bytes.

Bruce Conrad said...

How lucky you will be, to have all these pictures. When Elizabeth was that age, we had a professional photograph taken. We selected one from the several proofs--that was all we could afford. It was heart-breaking to know that the other proofs would just be destroyed.

My next post will be about a discovery of Elizabeth.

Josie said...

Wow, that was sort of starting to make sense until my strong distaste for math started to take over. Just today, when David and I dropped Josie off at Nancy's, I was commenting on how funny it was that so many in our family really hate math, when my brother is a total math genius. And David, also known as Number Man, could have been a math genius, too. In High School, he was doing the work and understanding it without a calculator and getting the same grades as other kids who used a calculator. You guys mathamaze me! (Not Josie, no matter what it says.)

Andrew said...

Hmm, just noticed that each time you add a bit, the number of possibilities doubles. It actually makes sense, that when you add one more digit that it would double, because there would still be all the original possibilities just with another 1 or 0 at the end.