To Documents

Positional Number Systems Tutorial

Primary reference: Wikipedia
http://en.wikipedia.org/wiki/Category:Positional_numeral_systems

A. Positional Number Systems

Since the beginning of elementary school, children use the decimal number system. We learn that the number 365 represents 3 hundreds, 6 tens and 5 ones. Formally, this is written as 365 = 3 × 10² + 6 × 10¹ + 3 × 10⁰. The meaning of each digit is determined by counting from the right: 5 on the right represents the ones (10⁰) place. Next, 6 represents the tens (10¹) place and 3 represents the hundreds (10⁰) place. The meaning of the digits in larger numbers is determined by this Powers of Ten Table.

The decimal system is one of many positional number systems that have been used historically. Actually any integer greater than one can be used as the base of a positional number system. For example, 124 in base 7 represents

1 × 7² + 2 × 7¹ + 4 × 7⁰ = 49 + 14 + 4 = 67

0   1   2   3   4   5   6   7   8   9

0   1   2   3   4   5   6

0   1   2   3   4   5   6   7   8   9   X   E  

A through F represent 10 through 15, respectively.

Not all number systems are useful, however. Here are some of the most important positional number systems, both historically and in current technology:

Base-2 (Binary)   The binary number system is crucial to the design and manufacture of modern electronic digital computers. Binary only requires the two digits 0 and 1. In fact the term bit, first used by John Tukey in 1946, is used to denote a binary digit. A bit can conveniently represent the logical values False or True, Off or On, Not Present or Present, etc. Bits are important in Boolean Algebra, which is used to design modern computers. See section B (The Binary Number System) below for more details.

Base-3 (Tertiary)   Digits are 0, 1, 2. The tertiary number system is important in theoretical logic and computer science. A tertiary logic uses the three-valued logic values False, True and Indeterminate (Maybe). Historically, a base-3 system of hand positions was used by medieval adherants of Islam to count prayers. Using this system, a person could count to over 100 on one hand. In 1940, Thomas Fowler built a mechanical wooden tertiary calculating machine; in the late 1950s, an electronic tertiary computer was built at Moscow State University. However, after that, interest in tertiary electronic computers waned, because binary computers were simpler to design.

Base-4 (Quaternary)   Digits are 0, 1, 2, 3. Genetic DNA uses a quaternary encoding system to represent biological information. Geneticists traditionally use the digits A, C, G, T to record this information. Using the encoding

Nucleotide	Base-4 Digit
A	0
C	1
G	2
T	3

the nucleotide sequence GATTACA can be represented as 2033010₄.

Base-5 (Quinary)   Digits are 0, 1, 2, 3, 4. The quinary number system is a natural one for humans because there are five fingers on one hand. In the twentieth century, only the Luo people of Kenya and the Yoruba of Nigeria were still using the quinary number system.

The ancient Romans used a modified version of this system; it would be more accurately called a quinary-decimal system. Here are the symbols that they used:

Roman Numeral	Meaning
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

The Chinese version of the abacus also uses this quinary-decimal system.



Base-8 (Octal)   Digits are 0, 1, 2, 3, 4, 5, 6, 7. The Yuki native American language in California and the Pamean language in Mexico used octal number systems. More recently, the use of octal was common in the 1960s and 1970s for representing computer data. This was because the length of a computer word on the computers at that time (such as the IBM mainframe) used words that were 24 binary digits in length. At that time, octal was convenient because a group of three digits are easily translated into a single octal digit using the following table:

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

For example, using this table, the binary sequence 011 111 101 110 010 001 101 111₂ translates into 37562157₈. Users of the Unix computer operating system are familiar with the the octal system because they use it to set file permissions.

Base-10 (Decimal)   Digits are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.   The decimal number system is discussed at the beginning of this section. It is well known to the readers of this document.

Base-12 (Duodecimal or Dozenal)   Digits are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, X, E.   Since duodecimal requires twelve digits, whereas decimal only needs ten, two more digits must be invented, namely X for ten and E for eleven. A kooky organization called the Dozenal Society that thinks that the world should switch from base 10 to base 12. Read the information on their website for more details. One good reason that the duodecimal system is not a good idea is that it would be incompatable with the metric system.

Base-16 (Hexadecimal)   Digits are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F, where A through F represent ten through fifteen, respectively. Since modern digital computers use words containing 32 or 64 binary digits, four binary digits are easily translated into one hexadecimal or hex digit. Use this Hex Digits Table to accomplish the translation. For example, 0110 1101 1110 1001 1011 0111 1000 1010₂ translates to 6DE9B78A₁₆.

Base-20 (Vigesimal)   Digits are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F, G, H, I, J. A modified system uses 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F, G, H, J, K to avoid confusion between 1 and I. The Maya and Aztec cultures used vigesimal number systems. Other cultures (such as the Celtic, Basque and Breton) used modified base-20 number systems. Base-20 systems are rarely used today.

Base-60 (Sexagesimal)   Sixty distinct digits are required. The ancient Babylonials used a base 60 number system. See this article on Babylonian Numerals for details, including the actual symbols that were used to represent the sixty digits. Our system of time, where 60 seconds make up a minute and 60 minutes make up an hour dates all the way back to the ancient Babylonians.

Base-64 (Quadrosexagesimal)   Digits are: A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z. a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, /. Currently base-64 is used for transmitting binary data in a variety of applications, for example, client/server, cryptography, XML. The MIME (Multipurpose Internet Mail Extensions) system is a base-64 encoding system for email attachments like images and sound files. On the negative side, spammers can sometimes use base-64 to their advantage because anti-spam software often does not decode base-64 and therefore would not detect that encoded spam is present in a message.

Practice Problems

1. Convert the following numbers of various bases into decimal:
   1011₂   1201₃   2310₄   7325₈   53XE₁₂

2. Why is each of these numbers are illegal?
   1598₈   1111 0102 0101 0110₂   21240110₃

B. Unsigned Binary Numbers

Binary numbers are used to represent integer data in modern digital computers This section describes how to use binary numbers to represent nonnegative integers. In section C, we will see how negative integers are represented in computer data. Use the following Powers of Two Table. A bit is defined as one binary digit. One byte is defined as eight bits.

Example: Convert the one byte unsigned binary number 01101101₂ to decimal:
01101101₂ = 0 × 2⁷ + 1 × 2⁶ + 1 × 2⁵ + 0 × 2⁴ + 1 × 2³ + 1 × 2² + 0 × 2¹ + 1 × 2⁰ = 64 + 32 + 16 + 8 + 4 + 1 = 123.

This calcutation can be shortened to 01101101₂ = 64 + 32 + 16 + 8 + 4 + 1 = 123.

Example: Convert 59₁₀ to unsigned one byte binary.
Repeatedly subtract the largest power of two that is less than or equal to the number remaining. Stop when you reach 0:
59 - 32 = 27; 27 - 16 = 11; 11 - 8 = 3; 3 - 2 = 1; 1 - 1 = 0.
Thus 59 = 32 + 16 + 8 + 2 + 1 = 00111011₂.

Practice Problems

1. Convert these numbers to decimal:
   00101101₂   01010101₂   10011110₂

2. Convert these numbers to unsigned one-byte binary.
   79₁₀   117₁₀   239₁₀

C. Binary Addition

Binary addition uses these arithmetic facts:

0 + 0 = 0    1 + 0 = 1    0 + 1 = 1    1 + 1 = 10

1 + 0 + 0 = 1    1 + 1 + 0 = 10    1 + 0 + 1 = 10    1 + 1 + 1 = 11

Example: Perform the binary addition 00111001₂ + 00101011₂. Start from the right and obtain the following:

Carry	0	1	1	1	0	1	1	0
Value 1	0	0	1	1	1	0	0	1
Value 2	0	0	1	0	1	0	1	1
Result	0	1	1	0	0	1	0	0

Practice Problems

1. Perform these binary additions:
   00001111₂ + 00000110₂
   00101001₂ + 00011011₂
   00101001₂ + 00011011₂

D. Converting Between Binary and Hex

Example: Convert the hex number 2AE9₁₆ to binary. Look up each hex digit in the hex digits table to give 2 --> 0010; A --> 1010; E --> 1110; 9 --> 1001. Putting them together gives 0010101011101001₂.

Example: Convert the binary number 10111010₂ into hex. Look up each group of four digits in the hex digits table to give 1011 --> B; 1010 --> C. Putting these together gives BC₁₆.

E. Signed Binary Numbers

The unsigned binary representation can only be used for nonnegative integers. For negative integers, signed integers are needed. For signed integers, a binary number with its leftmost bit set to 0 represents a positive integer or zero. A binary number with its leftmost bit set to 1 represents a negative integer. Here are the meanings of the Meanings of Signed and Unsigned Integers. Note that half of the signed integers (from 00000000 to 01111111) are positive and the other half (from 11111111 to 10000000) are negative.

Signed integers work somewhat like the odometer of an car that runs backwards if the car travels in reverse. If a car with a decimal odometer starts at 000000 and backs one mile out of the dealership parking lot, the odometer will show 999999; the signed representation of -1 is 999999. Similary, if a car with a binary odometer starts at 00000000 and backs one mile out of the lot, the odometer will show 11111111; the signed one-byte representation of -1 is 11111111. Backing one more mile out of the parking lot causes the binary odometer to show 11111110, so the signed representation of -2 is 11111110. (Look again at the table comparing the signed and unsigned integers.)

Algorithm for Negating a Binary Number

1. ASCII Codes for Printable Characters

2. ASCII Codes for Nonprintable Characters

To convert the characters "!%TUNA9*>~" to binary ASCII, first convert the characters to hex ASCII by looking them up in the ASCII Table for Printable Characters. The following codes are obtained:

21 25 54 55 4E 41 39 2A 3C 7E

Translate each character to binary with the Hex Digits Table.

00100001 00100101 01011000 01010101 01001110 01000001 00111001 00101010 00111100 01111110

Example: Binary ASCII to Character

To convert the binary ASCII codes 00110010 00111010 00110011 00110000 to characters, first translate to hex (four bits per hex digit): 32 3A 33 30. Now look up these codes in the ASCII Table for Printable Characters to obtain "2:30"

Although ASCII is strictly designed for encoding American English characters, computers routinely encode characters from every major language (ancient and modern) in the world. The best system to use for encoding characters for languages other than English is the Unicode system. For more details, see the Unicode website www.unicode.org website.

Practice Problems

1. Convert this phrase into binary ASCII codes:
   When is 1 + 1 = 10?

2. Convert these binary ASCII codes into characters:
   01000111 01110010 01101111 01101111 01110110 01111001