Numbers and Numbering Systems • Jonathan Cook

Our normal use of numbers is always in the decimal, or base-10, numbering system. The digits of 0 to 9 represent the values directly representable in base-10 (in any base, the digits are always from zero to one minus the value of the base).

To represent larger values, our numbering systems use positional notation. In this scheme, a digit can represent a value larger than its direct value. Thus

329 == 300 + 20 + 9

The digits 3 and 2 do not represent three and two, but 300 and 20. This is because the position of the digit indicates a power of 10 by which the digit should be multiplied with. This is reprsented as a formula like:

329 = (3 * 100) + (2 * 10) + (9 * 1) == (3 * 10^2) + (2 * 10^1) + (9 *10^0)

The positional scheme is much better than, say, the Roman Numeral scheme, where each symbol represented a unique value no matter where in the number it existed (i.e., M=1000, D=500, C=100, L=50, X=10, V=5, I=1). For more information you can check out Wikipedia:Positional_notation.

So, the general scheme for a positional numbering system in base B is:

There are B unique symbols, representing the values 0 to B-1.
Digits in a number are multiplied by a power of B, starting at 0 on the right and increasing by 1 for each digit to the left.

Binary, Hex, and Octal, Oh My!

The number systems we will use in this class are:

Base-10, or decimal: digits 0-9, and each place is a multiple of 10.

Base-8, or octal: only digits 0-7, and each place is a multiple of 8.

Base-16, or hexidecimal: digits 0-9,A-F, and each place is a multiple of 16.

Base-2, or binary: only digits 0 and 1, and each place is a multiple of 2.

special note: we call binary digits "bits", and often say "hex" rather than hexadecimal

For more information see Wikipedia:Hexadecimal, Wikipedia:Octal, and Wikipedia:Binary.

Because we use the same digits in different numbering systems, we need some way of knowing which number system we are using. In a math course we would use a subscript to show the base, such as:

1011~2~ = 11~10~

Notice that both values above only use the digits 0 or 1, but represent the same number (eleven) with different strings of those digits, because of the different base.

Writing Values in Plain Text

Because simple text files on computers do not represent subscripts, we will need to use special symbols to indicate which base we are working in. The AVR tools use the notation that is used in Unix, C, C++, Java, and many other places:

A hexadecimal number has a leading "0x" attached to the number.

e.g., 0x4f2a is the hexadecimal number for the decimal value 20266

An octal number has just a leading "0" attached to it, and then the number itself.

e.g., 076 is decimal 62, and 089 is not a number!

Sometimes (not often), a binary number has "0b" in front of it, and then the number

e.g., 0b10110 is decimal 22
usually in Unix/C/C++/Java you have to convert a binary number to something else (like hex), then use it
in class it will typically be clear when we are writing binary, and when it is not we will use a '%' sign in front of the number.

Converting Values between Number Systems

Computer Scientists use octal and hexadecimal a lot because these systems easily convert to binary, whereas decimal does not.

For octal, each octal digit is exactly 3 binary digits

For hexadecimal, each hex digit is exactly 4 binary digits

For decimal, there is no exact mapping, so you have to do some arithmetic to convert to binary

In octal, 046 is binary 100110, the first three (100) is the 4, and the second three (110) is the six

octal 036 is binary 011110; the first three digits change, but the last three do not.

To convert between hex/octal/binary do the following simple things:

From hex to binary, write the four bits that are equivalent to the hex digit, in exactly the same position in the number as the hex digit. Always write four bits!
From octal to binary, write the three bits that are equivalent to the octal digit, in exactly the same position in the number as the octal digit. Always write three bits!
From binary to hex, group the bits into fours, starting at the right. Then translate each group into one hex digit, in the same position as the group of four bits.
From binary to octal, group the bits into threes, starting at the right. Then translate each group into one octal digit, in the same position as the group of three bits.
If on the leftmost side of the binary number there are not enough bits to make a complete group, it is OK to add 0's to the left.

Unfortunately, we think in decimal, so we often need to convert numbers to and from decimal. This takes a little more work.

Converting to decimal is very easy: just multiply each digit by the power of the base for that position

Octal example: 0473 = (4*8^2)+(7*8^1)+(3*8^0) = (4*64)+(7*8)+(3*1) = 315 in decimal
Binary example: %1011 = (1*2^3)+(0*2^2)+(1*2^1)+(1*2^0) = (1*8)+(0*4)+(1*2)+(1*1) = 11 base 10
Hex example: 0xC6A = (12*16^2)+(6*16^1)+(10*16^0) = (12*256)+(6*16)+(10*1) = 3178 base 10

Converting from decimal to another base is a bit harder: must repeatedly divide by the base we are converting to. The remainders from these divisions will be our digits in the converted number (but they are backwards!)

Algorithm:
1. divide number by base, get quotient and remainder. This remainder is the rightmost digit.
2. Now divide qotient by base, get new quotient and remainder. This remainder is second-rightmost digit.
3. Keep dividing each new quotient by the base to get the next rightmost digit. Stop when new quotient is 0 and remainder is the old quotient; this is the final, leftmost digit of the number in the new base. (shortcut: when you see a new quotient that is less than the base, this is your final leftmost digit)
Octal example: convert decimal 93 into octal. We divide 93 by 8 and get 11 with a remainder of 5. We then take the quotient and again divide by 8. So 11 divided by 8 is 1 with a remainder of 3. We do the same again, so 1 divided by 8 is 0 with a remainder of 1. We stop when we have a quotient of 0. Now we take those remainders (5,3,1) and reverse them for our octal number of 0135, which is the conversion of decimal 93 into octal. We can check that by converting back (1*64 + 3*8 + 5 = 64+24+5 = 93 base 10).
Binary example: convert decimal 21 to binary. Divide 21 by 2 and get 10, remainder 1. Divide 10 by 2 get 5 remainder 0. Divide 5 by 2 get 2 remainder 1. Divide 2 by 2 get 1 remainder 0. Divide 1 by 2 get 0 remainder 1. Done, reverse remainders and get %10101

Why is this important?

But why do we need binary?

Well, in short, because computers operate in binary

Computers are electrical machines

Things like toasters, even (older) TVs and radios, are analog devices

That is, the electrical signals vary continuously

A computer is a digital electrical device

It operates on electrical values that are at discrete levels
Furthermore, all computers operate on two discrete levels of electricity

These two levels are interpreted as the binary digits 0 and 1

Thus, in a computer, all values are in binary, and all operations (including addition, multiplication, etc.) are performed in binary

Each binary digit is called a bit

An eight-bit binary value is called a byte

Most CPU's these days call a 32-bit value a word

But not the CPU we will be programming in this class!