Back to DFS's Pascal Page

Numeration Systems

(Preliminary)

Follow these fast links:

• Binary
• Octal
• Hexadecimal
• Tables, Proofs, etc.
  • Counting
    • Counting in Binary
    • Counting in Different Bases
    • Web Page: Counting in Four Bases
  • Addition and Multiplication
    • Table of Decimal Addition Facts
    • Table of Binary Addition Facts
      Web Page: Binary Addition Practice
    • Table of Binary Multiplication Facts
      Web Page: Binary Multiplication Practice
    • Table of Octal Addition Facts
      Web Page: Octal Addition Practice
    • Table of Octal Multiplication Facts
      Web Page: Octal Multiplication Practice
    • Table of Hexadecimal Addition Facts
      Web Page: Hexadecimal Addition Practice
    • Table of Hexadecimal Multiplication Facts
      Web Page: Hexadecimal Multiplication Practice
    • Web Page: Generating Addition and Multiplication Charts
  • Conversion
    • Binary-Decimal Conversion
    • Binary-Octal Conversion
      Web Page: Binary-Octal Conversion Proof
    • Binary-Hexadecimal Conversion
      Web Page: Binary-Hexadecimal Conversion Proof

Three numeration systems, binary, octal and hexadecimal, are used when dealing with the internal workings of computers. To be a knowledgeable, efficient programmer requires at least a rudimentary understanding of how they work and how they are interrelated.

Back to Top

Binary

The most basic computer unit of data that has an address assigned to it is the byte. It consists of eight (8) bits, each of which represents a binary digit. The numeration system used in the computer is known as Binary, or Base 2.

Our usual numeration system is known as decimal or Base 10.

It would seem natural that humans would want to use the numeration system with which they are familiar. However, the computer designers realized that computers and binary were made for each other. Electricity has two states: on and off. A binary digit has two possible values: 1 and 0.

It was obvious that 1 could represent on and 0 could be off. Consider the following four basic binary addition facts,

  0   0   1    1
 +0  +1  +0   +1
 --  --  --   --
  0   1   1   10

which could be arranged in the following table.

Back to Top

Back to Top

Using these addition facts, we can easily count in binary up to 1000₂, the equivalent of 8₁₀. The red digits indicate carrying. You will note that carrying already takes place for the addition 1 + 1, when we get the first group of 2.

     1       11         1        111
  0   1  10   11  100  101  110   111
 +1  +1  +1   +1   +1   +1   +1    +1
 --  --  --  ---  ---  ---  ---   ---
  1  10  11  100  101  110  111  1000

Compare the above chart with the one for decimal below.

Back to Top

Almost all would think that this table for decimal is extremely simplistic, because they already know it by heart. However, it has twenty-five times as many facts as the one for binary. Since any numerical value which can be expressed in one system can be expressed in the other, computer designers decided to use binary because they would need to make the computer handle so many fewer addition facts. This would obviously make their job as designers much simpler.

The only real problem with using binary was that the number of digits required to represent a value rose very quickly as the value increased. The table below shows the first eight place values for binary digits.

Back to Top

All values up to 255₁₀ can be represented by combinations of 1s and 0s in binary numbers using up to a total of eight digits. For example, 15₁₀ is equivalent to 1111₂ based on the sum of the place values of the 1s digits.

Back to Top

Octal

Since numbers represented in binary quickly have a great number of digits (255₁₀ = 11111111₂), two other systems are used to make things easier for humans, Octal (Base 8) and Hexadecimal (Base 16). The following table illustrates counting using the whole number values from 0₁₀ to 20₁₀ in all four bases.

Back to Top

Notice that the number of the base indicates the total number of different symbols used in that system.

Octal was used originally for two reasons:

• With larger values it requires only a third as many digits to represent a value as does binary;
  • While 1010₂ is equal to 12₈ (a saving of 50%), 111111111₂ is equal to 777₈ (a saving of 2/3).
  • Using fewer digits to represent a value makes it easier and faster for humans to communicate amongst themselves. Saying seven-seven-seven is much less taxing than saying one-one-one-one-one-one-one-one-one. It is also much more difficult to misspeak or mishear when using, say, five octal digits instead of 15 binary ones and zeros.
• It is easy to convert between octal and binary.
  • Since 8 is a power of 2 (2³), a simple mathematical relationship can be exploited to do the conversion.
  • Each grouping of three binary digits can be converted directly to a single octal digit. For example, the following conversion

    101 1102

    =

    5 68

    can be performed by a simple lookup in the table below.

    Back to Top

    Binary-Triplet/Octal Conversion
    Binary	000	001	010	011	100	101	110	111
    Octal	0	1	2	3	4	5	6	7

    The mathematical relationship between the octal and binary systems can easily be demonstrated using the concept of place value.

    1011102	=	Digit-by-digit conversion to base 10 1 x 25 + 0 x 24 + 1 x 23 + 1 x 22 + 1 x 21 + 0 x 20
    	=	Extract common factors 23(1 x 22 + 0 x 21 + 1 x 20) + 20(1 x 22 + 1 x 21 + 0 x 20)
    	=	Simplify 8(4 + 0 + 1) + 1(4 + 2 + 0)
    	=	Simplify 8(5) + 1(6)
    	=	Convert to powers of 8 81(5) + 80(6)
    	=	Commutative Property 5 x 81 + 6 x 80
    1011102	=	Digit-by-digit conversion to base 8 568 Q.E.D.

    Fortunately, for us humans, we do not need to use this latter method. All we have to do is use the table above, which can be easily memorized (or generated as needed).

Many programmers became very proficient in their use of octal. Not only could they convert between binary and octal with ease, they could also do arithmetic in octal. A quick look at this table of octal addition facts shows that they did not have to learn much that was different from the decimal addition facts they already knew.

Back to Top

Two things conspired against the use of octal as the preferred shorthand for binary:

• The amount of memory used in a computer increased rapidly, requiring ever longer strings of octal digits to represent memory addresses
• The development of the 8-bit byte, 8 not being evenly divisible into groups of three

Back to Top

Hexadecimal

The introduction of the 8-bit byte ensured the use of hexadecimal, Base 16, in computing. Its nickname is hex. The byte could be treated as being composed of two 4-bit units, which are called nibbles -- something intermediate between a little bit and a big byte.

Life is filled with trade-offs. Making one thing easier or better often requires learning more. Consider these facts.

• Hexadecimal requires 16 different symbols, six more than we have available from decimal.
• Hexadecimal uses a quarter the number of digits needed to represent a value in binary.
• Hexadecimal-binary conversion requires a table twice as large as that for octal-binary; this makes visual scanning for a value and memorization more difficult.
• 64 Meg or 128 Meg of RAM in a personal computer is now not uncommon.
• Operating systems on personal computers are now 32-bit.

To directly address 128 Meg of RAM requires an address 28 bits long. This would result in an octal representation of 10 digits and in hexadecimal of 7. CPUs can now have 32 bits in a register. This would take 11 octal digits or just 8 in hexadecimal.

Binary still remains important. A single bit can serve as a boolean variable. Finding the particular bit which is being used for a boolean out of 32 bits is not easy and the programmer is prone to making mistakes. It is much easier to find the value of a specific bit by scanning the hex value for the nibble which contains it and then do the hex-digit to binary conversion using the chart below.

To convert from binary to hex, break up the binary number into groupings of four binary digits, i.e., nibbles. Then using the table below, find the corresponding hex digit for each nibble, e.g.,

1111 1101 0000 01102

=

F D 0 616

Back to Top

There is a major downside to using hexadecimal -- there are a lot more addition facts to learn. The use of symbols with unfamiliar values (A, B, C, D, E, F) only compounds the problem. Thank goodness for hand-held calculators!

Back to Top

Back to Top

The eight bits in a byte can be used to represent 256 different values, from 0₁₀ to 255₁₀ (in decimal) or from 0₁₆ to FF₁₆ (in hexadecimal). Hex still has a role to play at the byte level. It is worth knowing hex and its relationships to binary and decimal.

Back to Top