Chapter 10: Counting like a Computer

Counting

Counting like a Human

In many ways, computers count just like humans. So, before we start learning how computers count, let's take a deeper look at how we count.

How many fingers do you have? No, it's not a trick question. Humans (normally) have ten fingers. Why is that significant? Look at our numbering system. At what point does a one-digit number become a two-digit number? That's right, at ten. Humans count and do math using a base ten numbering system. Base ten means that we group everything in tens. Let's say we're counting sheep. 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Why did we all of a sudden now have two digits, and re-use the 1 ? That's because we're grouping our numbers by ten, and we have 1 group of ten sheep. Okay, let's go to the next number 11. That means we have 1 group of ten sheep, and 1 sheep left ungrouped. So we continue - 12, 13, 14, 15, 16, 17, 18, 19, 20. Now we have 2 groups of ten. 21 - 2 groups of ten, and 1 sheep ungrouped. 22 - 2 groups of ten, and 2 sheep ungrouped. So, let's say we keep counting, and get to 97, 98, 99, and 100. Look, it happened again! What happens at 100? We now have ten groups of ten. At 101 we have ten groups of ten, and 1 ungrouped sheep. So we can look at any number like this. If we counted 60879 sheep, that would mean that we had 6 groups of ten groups of ten groups of ten groups of ten, 0 groups of ten groups of ten groups of ten, 8 groups of ten groups of ten, 7 groups of ten, and 9 sheep left ungrouped.

So, is there anything significant about grouping things by ten? No! It's just that grouping by ten is how we've always done it, because we have ten fingers. We could have grouped at nine or at eleven (in which case we would have had to make up a new symbol). The only difference between the different groupings of numbers is that we have to re-learn our multiplication, addition, subtraction, and division tables for each grouping. The rules haven't changed, just the way we represent them. Also, some of our tricks that we learned don't always apply, either. For example, let's say we grouped by nine instead of ten. Moving the decimal point one digit to the right no longer multiplies by ten, it now multiplies by nine. In base nine, 500 is only nine times as large as 50.

Counting like a Computer

The question is, how many fingers does the computer have to count with? The computer only has two fingers. So that means all of the groups are groups of two. So, let's count in binary - 0 (zero), 1 (one), 10 (two - one group of two), 11 (three - one group of two and one left over), 100 (four - two groups of two), 101 (five - two groups of two and one left over), 110 (six - two groups of two and one group of two), and so on. In base two, moving the decimal one digit to the right multiplies by two, and moving it to the left divides by two. Base two is also referred to as binary.

The nice thing about base two is that the basic math tables are very short. In base ten, the multiplication tables are ten columns wide, and ten columns tall. In base two, it is very simple:

 Table of binary addition + |  0  |  1 --+-----+----- 0 |  0  |  0 --+-----+----- 1 |  1  | 10 Table of binary multiplication * |  0  |  1 --+-----+----- 0 |  0  |  0 --+-----+----- 1 |  0  |  1 

So, let's add the numbers 10010101 with 1100101:

    10010101 +   1100101 -----------    11111010 

Now, let's multiply them:

         10010101      *   1100101      -----------         10010101        00000000       10010101      00000000     00000000    10010101   10010101  ---------------   11101011001001 

Conversions between Binary and Decimal

Let's learn how to convert numbers from binary (base two) to decimal (base ten). This is actually a rather simple process. If you remember, each digit stands for some grouping of two. So, we just need to add up what each digit represents, and we will have a decimal number. Take the binary number 10010101. To find out what it is in decimal, we take it apart like this:

      1    0    0    1    0    1    0    1      |    |    |    |    |    |    |    |      |    |    |    |    |    |    |    Individual units (2^0)      |    |    |    |    |    |    0 groups of 2 (2^1)      |    |    |    |    |    1 group of 4 (2^2)      |    |    |    |    0 groups of 8 (2^3)      |    |    |    1 group of 16 (2^4)      |    |    0 groups of 32 (2^5)      |    0 groups of 64 (2^6)      1 group of 128 (2^7) 

and then we add all of the pieces together, like this:

 1*128 + 0*64 + 0*32 + 1*16 + 0*8 + 1*4 + 0*2 + 1*1 = 128 + 16 + 4 + 1 = 149 

So 10010101 in binary is 149 in decimal. Let's look at 1100101. It can be written as

 1*64 + 1*32 + 0 * 16 + 0*8 + 1*4 + 0*2 + 1*1 = 64 + 32 + 4 + 1 = 101 

So we see that 1100101 in binary is 101 in decimal. Let's look at one more number, 11101011001001. You can convert it to decimal by doing

 1*8192 + 1*4096 + 1*2048 + 0*1024 + 1*512 + 0*256        + 1*128 + 1*64 + 0*32 + 0*16 + 1*8 + 0*4        + 0*2 + 1*1 = 8192 + 4096 + 2048 + 512 + 128 + 64 + 8 + 1 = 15049 

Now, if you've been paying attention, you have noticed that the numbers we just converted are the same ones we used to multiply with earlier. So, let's check our results: 101 * 149 = 15049. It worked!

Now let's look at going from decimal back to binary. In order to do the conversion, you have to divide the number into groups of two. So, let's say you had the number 17. If you divide it by two, you get 8 with 1 left over. So that means there are 8 groups of two, and 1 ungrouped. That means that the rightmost digit will be 1. Now, we have the rigtmost digit figured out, and 8 groups of 2 left over. Now, let's see how many groups of two groups of two we have, by dividing 8 by 2. We get 4, with nothing left over. That means that all groups two can be further divided into more groups of two. So, we have 0 groups of only two. So the next digit to the left is 0. So, we divide 4 by 2 and get two, with 0 left over, so the next digit is 0. Then, we divide 2 by 2 and get 1, with 0 left over. So the next digit is 0. Finally, we divide 1 by 2 and get 0 with 1 left over, so the next digit to the left is 1. Now, there's nothing left, so we're done. So, the number we wound up with is 10001.

Previously, we converted to binary 11101011001001 to decimal 15049. Let's do the reverse to make sure that we did it right:

 15049 / 2 = 7524    Remaining 1 7524 / 2 = 3762     Remaining 0 3762 / 2 = 1881     Remaining 0 1881 / 2 = 940      Remaining 1 940 / 2 = 470       Remaining 0 470 / 2 = 235       Remaining 0 235 / 2 = 117       Remaining 1 117 / 2 = 58        Remaining 1 58 / 2 = 29         Remaining 0 29 / 2 = 14         Remaining 1 14 / 2 = 7          Remaining 0 7 / 2 = 3           Remaining 1 3 / 2 = 1           Remaining 1 1 / 2 = 0           Remaining 1 

Then, we put the remaining numbers back together, and we have the original number! Remember the first division remainder goes to the far right, so from the bottom up you have 11101011001001.

Each digit in a binary number is called a bit, which stands for binary digit. Remember, computers divide up their memory into storage locations called bytes. Each storage location on an x86 processor (and most others) is 8 bits long. Earlier we said that a byte can hold any number between 0 and 255. The reason for this is that the largest number you can fit into 8 bits is 255. You can see this for yourself if you convert binary 11111111 into decimal:

 11111111  = (1 * 2^7) + (1 * 2^6) + (1 * 2^5) + (1 * 2^4) + (1 * 2^3)           + (1 * 2^2) + (1 * 2^1) + (1 * 2^0) = 128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = 255 

The largest number that you can hold in 16 bits is 65535. The largest number you can hold in 32 bits is 4294967295 (4 billion). The largest number you can hold in 64 bits is 18,446,744,073,709,551,615. The largest number you can hold in 128 bits is 340,282,366,920,938,463,463,374,607,431,768,211,456. Anyway, you see the picture. For x86 processors, most of the time you will deal with 4-byte numbers (32 bits), because that's the size of the registers.