This is the first article in a series whose intention is to have the reader able to understand binary, octal, and hexadecimal; three radices of great importance to contemporary computer theory. By the end of this series, you should be able to read and convert integer values into binary, octal, and hexadecimal, perform arithmetic on all three representations, understand basic Boolean operations, and otherwise have a further appreciation of the power of binary.
A Brief History Of Counting
We rarely think about counting itself in our daily usage of numerals, having learned from an early age how to do so. Our most common system of counting, the Hindu-Arabic (or Indo-Arabic) numeral system, was developed and adopted over a long period of time. It’s strange to consider, but this decimal numeral system wasn’t always around and certainly wasn’t the first.
To understand the concept of radix, which is an abstraction particular to a positional numeral system such as the Indo-Arabic, we have to understand how such a system came about. To understand how and why this system came about and is used, we have to understand the intellectual foundations of counting itself.
The Quantity Abstraction
The concept of a number is an abstraction. The idea is that a given identifier, in this case, a number, indicates the quantity of a set of individual elements. For instance, say we have these symbols:
Without any process of abstraction, this collection of symbols presents to us a gathering of unique entities, each separate from the other. Our first abstraction is to note that some of the symbols have similar characteristics. We can see that some of the symbols are a particular color, and likewise, we can note that some of the symbols have the same overall shape.
Abstraction is this conscious process through which we identify particular characteristics of entities while ignoring the specific measures of those characteristics. By identifying the trait of hue, and ignoring all other aspects, we come up with color, no matter the shape or size. By identifying a unique look, and ignoring all other aspects, we come up with shape, no matter the size or color. Using that process we can say multiple symbols are all green, or all square in the above diagram.
Counting is a similar process. Now we identify a new trait, that of amount. Focusing purely on the characteristic of amount gives rise to the abstraction of quantity. Each symbol considered by itself is a single thing. Single here is an instance of the abstraction of quantity. If we then consider the entire diagram we can see that there are seven things. Seven here is an instance, arbitrarily named, of the same abstraction of quantity. This abstraction, and its infinite instances, is what we know as counting.
In the diagram above I can see there are four green shapes, and three blue shapes. I can also see there are two squares and five triangles. Overall, there are seven shapes in total. This is counting in practice.
In mathematical terms what we are doing in these cases is determining the size of a set. A set is a collection of elements, and the quantity of that set is the number of those elements. Each colored shape is an element and the numbers three or five correspond to the quantity of them in a given set.
It’s useful to be able to acknowledge and assign names to instances of the abstraction of quantity (numbers). Each language has its own way of doing this. In English, the most basic names are one, two, three, and so on up until nine. For instance, with the knowledge that I have four arrows left, I can gauge my ability to hunt, or knowing I have seven pies can tell me how many people I can invite to dinner. However, what do we do when a) we want to record this information and b) the numbers become so large they become difficult to process?
Keeping Record Of Quantity
Let’s first tackle the recording of quantity. In pre-literary history, people often used various body parts to assist them in counting. We still do this today when we employ our fingers, for example, to count up to ten. However, once the quantity to count surpasses memorable body parts, accuracy suffers.
The Unary Numeral System
People needed something external to themselves that could persist. One way of creating an external measure was to use objects, or marks, in such a way that there were equal marks for equal quantity.
This system is known as a unary numeral system: to represent a quantity, a given symbol is repeated the same amount of times. This was useful for recording purposes, as you could indicate a quantity without having to have what you were counting present, but it presented serious shortcomings.
Imagine looking at a disorganized series of one-hundred twenty-seven dots and determining how many dots exist. To do so, you’d have to recount them again to be sure. To make this recount easier, and much simpler, a method of marking known as tally marks was used.
In this system, marks are drawn together in clusters, each typically denoting a quantity of five. The diagrams below show four different systems of tally marks as they exist today:
These types of tally marks (and variations) are used most often in Europe, Australia, New Zealand, North America, and South Africa.
For regions where Chinese logograms (漢字/汉字) are used, mainly China and Japan, the character 正 is drawn repeatedly as it consists of five strokes.
In France, Spain, and Brazil it’s common to use squares with a slash such as this.
In the fields of forestry, the tally marks are often clustered in quantities of ten by including dots in the square as well as lines.
The key observation to take away from these tally marks is that of the clustering. With tally mark clusters we can suddenly start counting by fives or tens when counting the marks as opposed to one at a time. This idea of clustering together a quantity is useful, and, as we’ll see, is expanded upon.
The Sign-Value System In Clay
In ancient times, the remains of which were later found in the Zagros region of Iran, people called Sumerians developed methods of primitive accounting. Society required records of transactions of flock and grain and so recording methods were devised utilizing clay tokens and string. The method by which a given quantity was encoded onto strung-together clay is known as a sign-value system.
To create a record that represented three bales of hay, as a probably historically inaccurate example, they would bake three clay tokens with a symbol on them to represent hay and then string them together. These were later baked into a bulla (or hollow ball) to preserve their integrity from outside manipulations. In this example, one token represented one bale of hay.
However, this had its limitations. As the number of things increased, the more difficult it was to count with singular tokens, much like the unary system. To overcome this, different tokens were baked and assigned a larger sum. Using this method to scale up you’d end up with a token for one bale of hay, a token for five bales of hay, a token for ten bales, and so on.
Each different token was strung along into a sequence. To know what amount a given string of tokens represented, one would add up the numbers assigned to each. One ten bale token, one five bale token, and two one bale tokens would be equivalent to seventeen bales of hay. This process and encoding, where a given number is arrived at through the summation of each element, is known as sign-value notation.
You’ve probably noticed that the tally marks discussed before are in many ways much like the tokens. Different representations for different values, particularly the forestry example. Tally marks are a unary system with elements of sign-value. However, sign-value notation by itself, as we’ll see in the following example, can be more complex and nuanced than tally marks allow.
You are likely already familiar with sign-value notation! This notation later came to be used in Roman numerals. That notation, with a few added rules of subtraction, is probably the most famous sign-value system. In Roman numerals, an I represents a one, V a five, X a ten, L a fifty, and C is one hundred. The example clay sequence above would then translate similarly to XVII in Roman numerals.
The astute reader will notice here the beginning of a very important trend. Once again we see higher and more abstract values (those difficult to count in sequence) getting shortened or clustered together. In this case, the Sumerians in our example grouped five elements into one element, and so on.
The Rise Of Cuneiform
As history marched forward, the Sumerians gradually replaced the dull pointer they were using for their accounting with a reed stylus that could press wedge shapes into clay. This was an adoption of the wedge-shaped cuneiform writing they had also developed. These wedge-shaped numerical notations continued to retain the circular shape and sign-value notation they had inherited, but there were problems.
Up until that point, Sumerians had recorded amounts in various states of isolation and each city had come up with its own method of a sign-value notation using different values. The incompatibilities weren’t limited to location, even in one city there could be different systems for different concepts; one for discrete objects, one for ingredients, one for area, one for time, etc. Think about how today some of us continue to struggle to convert tablespoons to cups, and ounces to pounds. These different systems of quantity led to ambiguity when recorded in cuneiform. Without knowing the proper sign-value delineations being used, the marks would be meaningless.
The Sexagesimal Number System
Eventually, these systems began to converge to a single standard around 2100 BC. Two cuneiform marks, the vertical wedge, and a V-like shape called a chevron became dominant. Sign-value delineations also converged, and by 1950 BC, at the beginning of the Old Babylonian period, a new standard arose in the form of a sexagesimal number system.
This new sexagesimal number system debuted a counting innovation that so far has eluded us. In a sexagesimal system, one counts using alternating delineations of ten and six (hence sexagesimal), but in contrast to sign-value, one also pays attention to where a given value is in the sequence. This is known as positional notation or place-value notation.
In this system, one counts up to nine using vertical marks, but when you get to ten you draw a chevron on the side. You may repeat this four more times, creating four more chevrons and ultimately nine more vertical wedges to reach a value of fifty-nine. Fifty-nine then has five chevron marks and nine vertical marks. Past this point, you would begin again in another position. A vertical mark in that position would indicate a value of sixty, being the next value after fifty-nine.
At first, this method may sound alien, but millions of people every day feel the influence of this system when they count sixty seconds to a minute, sixty minutes to an hour, or three-hundred and sixty degrees to a circle. This numerical ghost of Babylonia continues to haunt us today.
The Culmination Of Clustering: Positional Notation
At last, we have uncovered the ultimate and most elegant consequence of value clustering. By paying attention to where a given numeral is in relation to others we can increase its value most efficiently to represent tens or even thousands as necessary.
You might notice that, although the Sumerian positional notation revolves around the number sixty, each position itself is divided up by the more familiar value of ten. Mathematically speaking there is a common theory that sixty was chosen because of its compactness and prime factorization (2 x 3 x 3 x 5). Due to this factorization, it is what is known as a superior highly composite number and is divisible by 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, and 30. A superior highly composite number is a number with the highest ratio of divisors to some power of itself in comparison to other numbers.
Place-Value Or Positional Notation
In positional notation, as opposed to sign-value notation, the placement of a numeral within a sequence of numerals helps determine that numerals value. In sign-value notation the numeral 5 is always equal to five, so 555 would be fifteen. In positional notation, the placement of a numeral, its position, indicates an additional value by which to be multiplied. To continue the example, 555 in decimal positional notation would equal five-hundred and fifty-five (5 x 100 + 5 x 10 + 5 x 1).
Using this notation a given numeral and its place is called a digit. 555 above would be three digits, while 12673 would be five digits. The actual place of a digit is called its position. The value represented by a series of digits is called a number. You can count the placements of digits from the right starting at 0. This count is called the index. The diagram below sums up these terms graphically:
But how do we determine the value by which a numeral is multiplied? How do we know that a 5 in index two is multiplied by 100 as opposed to say 256? To answer those questions we must develop a new parallel concept integral to positional notation: radix (also called the base). Radix is a Latin word for “root.”
Decimal, Or A Radix Of 10
We’ve outlined how the position of a numeral in positional notation denotes a value to be multiplied against that numeral for a final value. In the diagram above, for example, 6 is to be multiplied by 100 for a final value of 600. But, what are the values to be multiplied? How did we know to multiply by 100?
The easiest way to illustrate the concept of radix is to count. Let us employ the standard method of counting, decimal, to show what each value placement, or position, means. If we start at zero and count up in decimal, we eventually reach nine. What happens next involves numeral position and defines the concept of radix or base.
9 is the highest numeral in the decimal system, meaning that there are no other numerals to choose from when counting. So how do we count higher? Those familiar with decimal will naturally point out the value of 10.
Notice what was done here.
We replaced the original 9 with a 0 and wrote a new numeral 1 to the left of the 0. In positional notation, we understand that this 1 is in the “ten’s place” and is equal to ten. That is, it is equal to 1 x 10. Of course, we could also derive that from the fact that 10 is equal to 1 + 9.
Likewise, if we count up another 9 values we reach the value 19. What happens when we count 1 past 19? We replace the 9 with a 0, and then increment (add 1) the 1 to a 2. This indicates, as above, that we are now speaking of 2 tens (that is, twenty) added to a 0. We can continue this process until we have 9 tens and 9 ones: 99.
What happens when we count one more past 99?
Much like with the tens place we replace the two 9s with 0s and write an additional numeral 1 to the left of the previous digits. We end up with 100 which represents one hundred. That is, the 1 is now in the “hundred’s place” and is equal to one hundred.
As we count up, we continue this process and in doing so we end up with a “thousand’s place,” a “ten thousand’s place,” a “hundred thousand’s place,” a “million’s place” and so on.
You’ll notice that each time we create a new “place” or position, the value indicated by that position increases by a factor (power) of 10. It’s no coincidence that in decimal the highest numeral, 9, is one less than the factor by which we’re multiplying. In our scenario here, the factor of 10 is known as the positional notation’s radix or base. Decimal then is known as base 10 or having a radix of 10.
Radix is the factor by which our place values (the value indicated by a numeral’s position) increase. You might think that, with a radix of 10, this is an obvious concept that need not be heeded. However, things get interesting when we decide to change the radix to something other than 10.
What does that look like?
Let’s use a radix that is lower than 10, for example, a radix of 6. This means that each place value increases by a factor of 6. The first place value (starting at 0) is 1, giving us 60 = 1. The second place value (one to the left) is 61 = 6, the “sixth’s place.” This is in contrast to decimal, where it would be the “tens place.” The third place value (one more to the left) is 62 = 36 or the “thirty-sixth’s place.”
If the second place value is 6, as opposed to 10, that means that we can only count up to 5 in the “one’s place” before replacing it with a zero and incrementing one digit to the left. In this scheme, this radix, that means that 10 = 1 x 6 = 6 as opposed to ten, and likewise, if we counted up by 5 again and then added one more we’d get 20 = 2 x 6 = 12.
You’ll notice here that not only is the radix the factor by which the place values increase, but it is also equal to the number of unique numerals (including zero) that we use to count in that radix.
Mathematically we can generalize the place value properties of an arbitrary radix. Let us define the radix as b (we assume here b > 1) and a series of digits limited by that radix as d1d2d3…dn (0 ≤ di ≤ b). Here each instance of d, a digit, is denoted by the subscript. The value of this abstract series of digits is then equal to (d1 x bn-1) + (d2 x bn-2) + (d3 x bn-3) + … + (dn x b0). This is equivalent to saying that the radix has a “one’s place (b0),” a “b2‘s place”, a “b3‘s place,” and so on.
We can actually define the radix to be something other than a natural number. We can employ an algebraic number such as the golden ratio, a complex base using the imaginary unit i, a negative base (which allows us to represent negative numbers without a minus sign), and even the natural log e. The latter of these comes up later when we discuss the economical factors of radix.
Examples Of Positional Notation With Different Radices
Let’s see if we can show the concept of radix using a positional notation by example. In these examples, we’ll be representing the value 2067 in three different radices: 3, 7, and 10.
For a radix of 3, we have the numerals 0, 1, and 2 at our disposal. The place-values increase by a factor of 3 (the radix) as we travel left. This gives us the following place values:
We start on the left and subtract place values away from the total value with increasing granularity and precision. On the far left we start with 729 (36), then 243 (35), followed by 81 (34), 27 (33), 9 (32), 3 (31), and finally 1 (30). You can see how the indices of the positional notation correspond to the powers of the radix. In each of these place values, we can only count up to 2 (the radix minus 1).
In the diagram, you can see I have translated the value 2067 into base 3. Starting with 1458 (729 x 2) we add 486 (243 x 2), then 81 (81 x 1), 27 (27 x 1), 9 (1 x 9), and finally 6 (3 x 2) to get our value 2067. In the next post in the series, we’ll discuss exactly how I was able to do this conversion.
For a radix of 7, we have the numerals 0, 1, 2, 3, 4, 5, and 6 at our disposal. The place-values increase by a factor of 7 (the radix) as we travel left. This gives us the following place values:
On the far left we start with 343 (73), then 49 (72), followed by 7 (71), and finally 1 (70). In the diagram, you can see I have translated the value 2067 into base 7. We start on the left and subtract place values away from the total value with increasing granularity and precision. Starting with 2058 (6 x 343), we skip 49 (the remainder of our subtraction isn’t large enough) and then add 7 (1 x 7), and finally 2 (2 x 1) for a total of 2067.
Finally, for our familiar radix of 10, we have the full range of traditional numerals at hand: 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. The place-values increase by a factor of 10 (the radix) as we travel left. This gives us the following place values:
On the far left we start with 1000 (103), then 100 (102), followed by 10 (101), and finally 1 (100). In the diagram, you can see I have translated the value 2067 into base 10. We start on the left and subtract place values away from the total value with increasing granularity and precision. Starting with 2000 (2 x 1000), we add 60 (6 x 10), and finally 7 (7 x 1) to achieve a sum of 2067.
What’s To Come
Writing numbers using positional notation gives rise to some interesting properties. Before we go too much further, though, we’ll cover how to convert between decimal and the three major radices used in computer science: binary, octal, and hexadecimal. As the series progresses we’ll cover many of these fascinating facets including how to calculate the economy (efficiency) of a given radix, how to represent negative and fractional values, and even some non-standard positional notation systems such as balanced ternary.