An Introduction to Discrete Number Systems

Initial Concepts

Many people have probably never thought deeply about the mechanics of number systems. Indeed, some may not realize that there are other ways of representing numbers than the "decimal" number system commonly used worldwide.

"Decimal" is a base-10, weighted-placement number system. The base of a number system is determined by the number of distinct values a single digit can have. In decimal, those are 0 through 9, for a total of ten. Each digit of a number is thus a selection of one value from ten possibilities. When we place multiple digits side by side, there is a implicit ordering and scale to them; this is the weighted placement. Assuming integer (whole) values, the right-most digit has normal weight. Then, for every place moved to the left, the significance grows by a factor of ten. This is illustrated by the math shown below:

  6 =                           (6 x 10^0)
 96 =              (9 x 10^1) + (6 x 10^0)
496 = (4 x 10^2) + (9 x 10^1) + (6 x 10^0)

  6 =                           (6 x 1)
 96 =              (9 x 10)   + (6 x 1)
496 = (4 x 100)  + (9 x 10)   + (6 x 1)

Note that the caret symbol '^' represents exponentiation, such that "ten to the second" is written as 102. In the second half of the listing the powers are evaluated, for the sake of clarity.

The case of real (fractional) numbers is not much different, except that for digits that lie to the right of the decimal point the powers count down from zero instead of up. For this article, the focus is on integer values.

There is no reason why we must use ten symbols to represent numbers. If we had six fingers on each hand, we probably would have ended up with twelve symbols and thus base-12. If early civilization had decided to use both fingers and toes for counting, the world would operate on base-20. Ancient Babylon used base-60; ever wonder why there are sixty seconds in a minute, sixty minutes in an hour, and 360 degrees in a circle? The Babylonians also invented the structure of implicitly weighting the values based on their position.

Paradigm Shift

Suppose we used base-8 instead. What would numbers look like? Well, for one thing, we only need eight symbols for base-8. Any eight distinct symbols can be used. For convenient accordance with decimal, let's get rid of values eight and nine and select zero through seven. We'll call this base-8 number system "octal".

Now a practical issue arises. We implicitly understand numbers in decimal, but lack that implicit understanding for octal. Therefore, we don't know how to represent a particular number in octal. Fortunately, we can convert back and forth with simple arithmetic.

Start with the decimal value 100. Octal is base 8, so we begin with an integer division by 8. The quotient is 12 with a remainder of 4 (100 - 96). That quotient 12 is too large to represent with one octal digit (7 is the max), so we divide again. Twelve over eight provides a quotient of 1 and a remainder of 4 again. Divide once more to get a zero quotient with remainder 1. A quotient of zero is the sign to stop dividing and collect the remainders. If read in reverse order as obtained, they are one, four, and four: 144. Indeed, 100 decimal is 144 octal. Written in mathematical shorthand:

100 / 8 = 12 remainder 4
 12 / 8 =  1 remainder 4
  1 / 8 =  0 remainder 1

This same process can be used to covert from decimal to any other base of your choosing. Simply change the divisor to the same value as the target base. (Note that this method doesn't work for the fractional part of real numbers; that requires repeated multiplication instead of division.)

What if we want to run the reverse process, determining which decimal value an octal number represents? In that case we use the principle of expanding the value into its weighted placement form, as shown earlier. Perhaps we wish to know what octal value 5220 is in decimal. It is equivalent to:

5220 = (5 x 8^3) + (2 x 8^2) + (2 x 8^1) + (0 x 8^0)
5220 = (5 x 512) + (2 x  64) + (2 x   8) + (0 x   1)
5220 =    (2560) +     (128) +      (16) +       (0)

octal 5220 = decimal 2704

Notice that because the number is octal, we use base eight in the weighted placement expansion. Our result is "smaller" than the input value, and this is to be expected. When converting from a narrower base like octal to a wider base like decimal, the value will shrink because each decimal digit has greater information storage compared to each octal digit.

The math may have looked a little confusing because the values are not explicitly identified as octal or decimal. For this reason, it is typical to give a special notation or symbol to numbers written in bases other than ten. The C programming language interprets numbers with a leading 0 as octal, for instance. An "o" prefix is used for in some other contexts, as in o5220 = 2704. One further attempt was to use the letter q; q5220 = 2704. This eliminates the potential for confusing zero and the letter o. Non-alphabetic symbols can also be used. For instance, if asterisk * were to indicate octal, we would write *5220 = 2704. Choosing a good symbolic notation is difficult; this one would be confusing in situations where asterisk is used for multiplication. For rich text documents where subscripts can be used, it is common to suffix the number with a subscript indicating its base (ex: 52208 = 270410). This provides clear and effective presentation, but requires more effort to write and can't be used in plain text documents.

Elaboration and Exploration

Eight is clearly not the lowest base we could use. Seven, six, five, four, three, and two all work as well. Why not one? A "base-1" system is in effect just a tally counter. For each higher number, you add a mark, line, or glyph. Notably, this kind of counting is linear; as numbers grow the size of the number's representation grows at the same rate. This becomes impractical for large numbers -- imagine having to write out two thousand marks to add 400 to 600! The reason for the linear growth of base one is that one raised to any power is still just one.

The smallest useful base is thus base-2, also known as binary. With it, we get the benefit of exponential growth in the number of values represented as we add digits while needing just two distinct symbols. As a result, binary is easier to represent in hardware and became the basis for modern computer systems. Each binary digit, or bit, has only two possible values and thus only two possible states. Practically speaking, this means that each fundamental memory component -- be it a vacuum tube, a transistor, memristor, or an electron -- need only be able to represent and distinguish two states (instead of 5, 10, or whatever higher base you may choose). This generally implies less potential for error and a lower cost to produce each memory unit.

In binary, our only values for each digit are 0 and 1. This means that by the number 3, we are already into multi-digit numbers. A binary counting of the first eight numbers from zero reads: 0, 1, 10, 11, 100, 101, 110, 111. Simple, but effective. The two most common notations for identifying binary values are either using a 'b' as prefix or suffix, or using the percent symbol '%'. Binary value 1100 equals 12 can thus be written as %1100 = 12.

As one might guess, working with long strings of bits represented directly can become tiresome and inefficient, with even relatively small numbers requiring several digits. For that reason, higher bases that easily convert to-and-from binary are often used. Any base which is a power of 2 has the property of direct conversion; some collection of n bits will correspond one-to-one to a digit in the higher base. For instance, every digit in base-4 is equal to exactly two bits since 22 = 4.

Remember our good friend octal that was introduced earlier? Octal was frequently used in the early days of computing, since eight is the third power of two. This was an especially good fit when a byte was a collection of six bits, instead of the eight it is today. Each octal digit represented three bits perfectly, as this listing shows:

%000 = q0 = 0
%001 = q1 = 1
%010 = q2 = 2
%011 = q3 = 3
%100 = q4 = 4
%101 = q5 = 5
%110 = q6 = 6
%111 = q7 = 7
 Overflow : 8
 Overflow : 9

All was well; two octal digits represented one byte. Later, the length of a byte was changed to eight bits. Three octal digits, unfortunately, do not map one-to-one with eight bits. No matter what scheme we devise, one octal digit ends up with leftover unmapped values, similar to how eight and nine in the list above are unmapped values that overflow three bits. This issue caused a migration to base-16, also known as hexadecimal. Octal was mostly left behind and is today used only in a few odd contexts. (Probably the most common of those is Unix permissions, which use three octal digits for owner, group, and world.)

In the era of the eight bit byte, hexadecimal is king. Every four bits is one "hex" digit. (Take care not to use the abbreviation hex in contexts where base six would be plausible.) Wait a moment, though; sixteen is more than ten. Decimal doesn't have enough symbols to represent hexadecimal numbers!

This problem was circumvented by re-purposing symbols from elsewhere. While multiple schemes were originally devised, one became standard: using the initial letters of the English alphabet to represent the values 10 to 15. Starting at the beginning, A through F are the first six letters and thus became our chosen few:

%0000 = $0 = 0
%0001 = $1 = 1
%0010 = $2 = 2
%0011 = $3 = 3
%0100 = $4 = 4
%0101 = $5 = 5
%0110 = $6 = 6
%0111 = $7 = 7
%1000 = $8 = 8
%1001 = $9 = 9
%1010 = $A = 10
%1011 = $B = 11
%1100 = $C = 12
%1101 = $D = 13
%1110 = $E = 14
%1111 = $F = 15

Hexadecimal, much like octal, has several common symbolic notations. C uses a 0x prefix (ex: 0xFF). An earlier notation, frequently used by assembly languages, is the $ prefix (ex: $FF). An "h" or "x" prefix or suffix is also sometimes used. My preference, as used above, is for dollar prefix notation. It's short, simple, precedented, recognizable, and easy to parse. Some may worry about confusion with monetary values, but hexadecimal is unlikely to be used in contexts where that would be coherent.

For familiarity's sake, let's run through some quick conversion examples for hexadecimal.

1050 / 16 = 65 remainder 10
  65 / 16 =  4 remainder 1
   4 / 16 =  0 remainder 4

1050 = $41A
---------------------------

$840 = (8 x 16^2) + (4 x 16^1) + (0 x 16^0)
$840 = (8 x 256)  + (4 x 16)   + (0 x 0)
$840 = (2048)     + (64)       + (0)

$840 = 2112

Notice the implicit conversion from 10 to $A in the first example. After working with hexadecimal for a while, it becomes second nature to make these equivalent substitutions. It helps to start by memorizing that $A = 10 and $F = 15 so that the boundaries stick in your mind. Engineers and scientists who work directly with binary data on a regular basis use hexadecimal so much that they learn to do arithmetic directly in it, without any base conversion. This is much like how one begins to speak and write a non-native language fluidly and implicitly, as second nature.

Consideration of Limits

Why stop at base-16? Certainly, we could go higher. It is mainly a matter of practicality. The next good fit is 32 (25), meaning 32 distinct symbols are necessary. Using all the decimal digits and 20 letters of the alphabet would work. Base-64 can't be satisfied with just the decimal digits and English alphabet, even when using upper and lowercase. Two more symbols are required; the MIME base-64 encoding uses forward slash '/' and plus '+'. Of course, if we have trouble finding characters, we could look to other languages. There are tens of thousands of Han ideographs available in Chinese. Base-1024 anyone?

At some point, we cross a threshold where remembering which symbol corresponds to what value is too difficult to make mathematical operations convenient. Remember those Ancient Babylonians and their crazy base-60 system? It wasn't really all that crazy in practice; they didn't have sixty distinct symbols. They actually used just two symbols to implement that number system: a ten glyph and a one glyph. A number such as twenty-one would be written uses two tens and a one. Forty-three is four ten glyphs and three one glyphs. Clever. A reimplementation of decimal using such a similar scheme of 5s and 1s would allow you to efficiently represent all digits using just two glyphs. Perhaps five is a curve and one is a straight line. Nine would be the most difficult value to write; one curve and four lines.

Why, then, was there a decline in Babylonian-style number schemes? One reason may be that it provided slower digit recognition and a higher rate of error in reading and writing. Human beings are very good at pattern recognition, but not so great at rapidly counting and replicating sub-patterns. The chance of accidently using one too many or few glyphs is higher, especially in a long and tedious calculation where the sea of similar glyphs starts to blend and blur. In that sense, having a larger number of distinct glyphs is useful, up to a point.