Binary Arithmetic
by Tim Thurman
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Observe the preceding series of numbers. These are the commonplace numbers which we use almost every day for counting. Indeed, they are so familiar that you will be tempted not to look at them closely or think about them seriously; but do look at them and observe how they proceed, how they change. Think about the pattern they follow and how the series continues beyond what is listed above. Note that while we usually start counting at one, here we start at zero. Why? Because the pattern is more clear. We start at zero and "count to nine", producing the unique single-digit decimal series which is repeated in the "one's column" over and over again, indefinitely.
We can see that the pattern in the one's column will continue, but what of the next column to the left? In the familiar decimal system, this is called the "ten's column"; and the unique single-digit decimal series is repeated in this column, as it was in the one's column but with a slight difference, namely, each digit appears ten times before the next digit appears. That gives us ten ones concatenated with the single-digit decimal series to produce the "teens", then ten two's concatenated with the decimal series for the "twenties", and so on. Think for a moment about the third column that would eventually appear if we were to continue, i.e. if we were to count to 100. Here again we would see the single-digit decimal series repeated over and over in the one's column, and in the ten's column we would see each numeral of the decimal series repeated ten times before the appearance of the next numeral. In the third column the series would again be repeated indefinitely, but each numeral would appear one hundred times before the next numeral appears. So in the one's column a "1" appeared once as the decimal series was iterated; in the ten's column a "1" appeared ten times during one series' iteration, and in the "hundred's column" it would appear one hundred times. Will it then appear one thousand times in the "thousand's column", before we see a "2"? Of course, as we all know. We say that the number of times a digit will be repeated in each "place to the left" is increased by a power of ten. A "1" in the one's column appears "ten to the zeroth power" times (10^0 = 1), that is, one time; in the ten's column it appears "ten to the first power" times (10^1 = 10) or ten times; in the hundreds column, "ten to the second power" times (10^2 = 100); and so on. This pattern, though familiar, is worth noting, for we will have reason to recall it momentarily.
The ten single-digit numerals, "0" through "9", make up the symbols of our numbering system. No matter how high we count, we still use only these ten numerals in an ordered, repetitive pattern. These are Arabic numerals, the ten symbols which were adopted for numerals as the Arab culture became literate centuries ago. Other numeral systems have been used by various societies, but this one has become the modern, world-wide standard, universally adopted in literate countries today. An example of a different numeral system which is familiar to Western students is the system of Roman numerals, which uses selected Roman letters to double as numerals as well as alphabetic characters: I, II, III, IV, X, L, C, etc.
Our numbering system uses ten different numerals and is known as a decimal system (from decem, the Latin word for ten , cf also deka, Greek). Why are there ten numbers in the series? Why not six or nine? The answer is in your hands . . . literally. Had we no thumbs, for instance, we would undoubtedly have developed an octal (base 8) numbering system instead of a decimal one for our ordinary counting purposes. What would such a system look like? Assuming the same historical development and the same conventions in ordering the series, we can surmise that it would be similar to the decimal one:
0
1
2
3
4
5
6
7
10
11
12
13
14
15
16
17
20
21
22
This is, in fact, an octal system of numbering which is used today in computer science. Note its similarity to the familiar decimal system. The unique single-digit series is again repeated indefinitely in the one's column; only this time the series has eight numbers instead of ten. The decimal system is sometimes called base ten, and the octal system, base eight. So where is the eight in the series above, someone might ask. It's just where you would expect it, right after the seven, just as the ten is right after the nine in the first series. But that looks like a ten, you object. Absolutely right! In base ten a "10" is a ten, in base eight a "10" is an eight. What about base five? Right, "10" is five; and so on for numbering systems with other bases. (What about base twelve, you ask? Even there, a "10" is a twelve. With bases higher than ten, alphabetic characters are used to "fill in the gaps", i.e. A is ten and B is eleven.)
Now let's take a look at base two, what is known as the binary system. Just as there are ten numerals in the deci mal system, so are there two numerals in the bi nary system: "0" and "1". Using the principles we have been developing, take a pencil and paper and write down what you think would be the first three numbers in the binary series of numbers, i.e. starting at zero, count to two. You should have the following series:
0
1
10
Just as a "10" is a ten in base ten and a five in base five, in base two a "10" is a two. And two follows one, just as expected. We had ten numbers in the unique single-digit series in base ten, and eight numbers in the unique single-digit series in base eight. Likewise, we have two numbers in the unique single-digit series in base two. If the similarities continue, we can expect this series to be repeated indefinitely in the one's column. Indeed, with the addition of "three" the series becomes
0
1
10
11
We see that the pattern in the one's column continues: the two numerals that make up the unique single-digit binary series are repeated. What about the second "column" or "place", just to the left of the one's column? Here we see two and three represented by what look like ten and eleven to our "decimal eyes". Since these correspond in a way to the decimal teens, can we expect the next parts of this series to be the "twenties"? If so, we could expect "20" and "21" to be the next numbers in this series; but there is no numeral "2" in base two. We have just seen that two is represented in base two by "10". Do we then replace the "2" in "20" and "21" by "10" to get "100" and "101"? Yes! And we have
0
1
10
11
100
101
Can you guess the next number in the series? One way to think about it is to continue the analogy in which we said that "10" and "11" correspond to the decimal teens and "100" and "101" correspond to the decimal twenties. We could then expect the "thirties" to follow, and we would need a three concatenated with a zero. Since a three in binary is "11", we would have "110" as the next number in our series, which is correct. Another way to think about it is to notice that the numerals "0" and "1" alternate in the one's column but that they then come in pairs in the next column. The pattern is clearer if we show the first eight numbers in the series (and include leading zeros).
000
001
010
011
100
101
110
111
Recall the pattern that we discovered earlier in decimal numbers in which each column to the left goes up by a factor of ten. Similarly, in base two each column goes up by a factor of two, giving us (from the right) the one's column (2^0 = 1), the two's column (2^1 = 2), the four's column (2^2 = 4), the eight's column (2^3 = 8), and so on. Even the short series above shows the "0's" and "1's" alternating in the one's column but coming in pairs in the "two's column". In the "four's column" they even seem to be in groups of four, which is, indeed, the case. And in the eight's column they come in groups of eight. This is one of those interesting and handy quirks often found in numbers which has made mathematics so fascinating to many. It should prove helpful to you while learning the binary number system.
Take the binary number, 10011. Does it represent the quantity ten thousand eleven? No, of course not. We have already learned enough to know not to look on binary numbers with our "decimal vision". This number would represent that quantity only in the decimal system, not in the binary system, where it represents nineteen. But how are we to figure out that it is nineteen? We use a procedure analogous to that which we use in base ten; but in base ten it is automatic, in base two we have to do it deliberately. Recall that each column "goes up" by a factor of two, and then move through the number from right to left in the following fashion: for 10011, we have one 1, one 2, no 4's, no 8's, and one 16: 1 0 0 1 1
16 + 0 + 0 + 2 + 1 = 19
Now try 1100110: no 1's, one 2, one 4, no 8's, no 16's, one 32, and one 64: 1 1 0 0 1 1 0
64 + 32 + 0 + 0 + 4 + 2 + 0 = 102
nary. We have to ask first what is the largest power of two that will go into our number. Scanning the list of the first eight powers, we see that sixteen is the largest that will go into twenty-five. This means that the number twenty-five has one sixteen in it, so we will want a "1" in the 16's column of our binary number. It also means that the 16's column will be the left-most column in our binary number. So at this point we have:
1 ? ? ? ?16's 8's 4's 2's 1's
Next we subtract sixteen (the highest power so far) from our original number, giving a nine. We repeat the process: what is the highest power of two that goes into nine? Answer: eight. So twenty-five "has an eight in it", and we put a "1" in the 8's column:
1 1 ? ? ?16's 8's 4's 2's 1's
Now we subtract the eight from the nine, leaving one; and since one is the highest power of two which will go into one, we put a "1" in the 1's column:
1 1 ? ? 116's 8's 4's 2's 1's
The quantity twenty-five is thus broken down into three quantities: sixteen, eight, and one (16 + 8 + 1 = 25); and we have "1's" in the corresponding columns of our binary representation of this quantity. What of the 4's and the 2's columns? Surely you can now guess that they will contain "0's":
1 1 0 0 116's 8's 4's 2's 1's
Do the following as an exercise to familiarize yourself with these methods of converting between binary and decimal representation.
Binary --> Decimal Decimal --> Binary a. 1010100 ________ h. 5 _____________ b. 1010 ________ i. 9 _____________ c. 110011 ________ j. 19 _____________ d. 101111 ________ k. 22 _____________ e. 10001 ________ l. 31 _____________ f. 1111 ________ m. 32 _____________ g. 10000111 ________ n. 46 _____________ o. 67 _____________
Arithmetic operations are possible on binary numbers just as they are on decimal numbers. In fact the procedures are quite similar in both systems. Multiplication and division are not really difficult, but unfamiliarity with the binary numbers causes enough difficulty that we will introduce only addition and subtraction, which are quite easy.
Addition is almost as easy as "one and one is two". Indeed, there are only "zero and zero is zero", "one and zero is one", and "one and one is two":
0 0 1 1 + 0 + 1 + 0 + 1 ---- ---- ---- ---- 0 1 1 10
Notice that adding two single-digit "1's" produces a two-digit result, which means that we have to "carry" into the next place, just as with our familiar decimal addition. Let's take a simple example, two plus four equals six:
1 0+ 1 0 0-------- 1 1 0
Starting at the right column, zero plus zero equals zero, one plus zero equals one, and zero plus one equals one. Too easy; we didn't even have to carry. Let's try three plus five equals eight:
1 1+ 1 0 1--------1 0 0 0
Starting at the right, one plus one equals two: bring down the zero, carry the one; (now in the 2's column) one plus zero equals one, plus the one carried equals two: bring down the zero, carry the one; (now in the 4's column, the leading or implied) zero plus one equals one, plus the one carried equals two: bring down the zero, carry the one (into the 8's column). Here is a final example to show how to handle a "three", eleven plus seven equals eighteen:
1 0 1 1+ 1 1 1----------1 0 0 1 0
Starting at the right, one plus one equals two: bring down the zero, carry the one; (2's column) one plus one equals two, plus one carried equals three ("11"): bring down the one, carry the one; (4's column) zero plus one equals one, plus one carried equals two: bring down the zero, carry the one; (8's column) one plus zero equals one, plus one carried equals two: bring down the zero, carry the one (into the 16's column). Now try the following as exercises.
a. 1 0 1 b. 1 1 1 c. 1 0 1 0 + 1 0 + 1 0 + 1 1 0 ----- ----- ------- d. 1 0 1 0 e. 1 0 1 0 f. 1 0 1 1 + 1 0 1 0 + 1 1 1 1 + 1 0 1 --------- --------- ------- g. 1 1 1 1 0 h. 1 0 0 1 1 0 i. 1 0 1 1 1 0 + 1 1 1 0 + 1 1 0 1 + 1 0 1 --------- ----------- -----------
Exercise 1 Exercise 2 a. 84 h. 101 a. 111 b. 10 i. 1001 b. 1001 c. 51 j. 10011 c. 10000 d. 47 k. 10110 d. 10100 e. 17 l. 11111 e. 11001 f. 15 m. 100000 f. 10000 g. 135 n. 101110 g. 101100 o. 1000011 h. 110011 i. 110011