Number Systems


For a positional numbering system, each digit represents how many items in the next higher power of the base.  That is, the value of a number d3d2d1d0 in base b is the sum of di * bi for all the digits in the number.  An example in base 10 seems trite and obvious, but let's look at the value of 1723.  The value is 1*103 + 7*102 + 2 * 101 + 3 * 100.

Let's turn to counting on fingers, since that is how we learned the first time.  All fingers down means 0.  Each successive finger that comes up represents a value one higher than the value before.  We count 1 2 3 4 5 6 7 8 9 10, starting with one finger up, raising one for each successively higher value, until all fingers are up and we call that 10 (a value not representable by a single digit).
 

Base 5 Numbers and addition

So let's switch to base 5, which we can think of as a natural base for one hand.  The fingers go up, one at a time, counting 1 2 3 4 and then when they are all up, we use the value 10 (just as before).  In base 5, we can make up numbers from the 5 digits (or more properly, something like quints) 0 1 2 3 and 4.  Some things stay the same, 2 + 2 = 4, but 4 + 1 = 10, and 4 + 2 = 11.  Here's an addition table
 
 
+
0
1
2
3
4
0
0
1
2
3
4
1
1
2
3
4
10
2
2
3
4
10
11
3
3
4
10
11
12
4
4
10
11
12
13

4+4=13.  Sounds weird, but look at the values.  1 * 51 + 3 * 50 = 8.  135 = 810.
So, the way to add is the same as in base 10, it's just that a carry operation happens with lower values.  An example is adding 4043 to 234.
 
 

4043
+234
====
4332

Starting on the right and using the table above, 3+4 = 12, so we write down the 2 and carry the 1.  4 + 3 + 1 = 13, so we write down the 3 and carry the 1.  0 + 2 + 1 = 3.  4 + 0 = 4.

Base 6 Numbers and Multiplication

Let's add one more digit to the mix, so now we have 0 1 2 3 4 and 5, allowing us to express values in base 6.  I like to think about base 6 as if we had thumbs on both sides of our hands.  Here is the single digit multiplication table for base 6.  You can build it from successive adding (the definition of multiplication, right?).
 
 
*
0
1
2
3
4
5
0
0
0
0
0
0
0
1
0
1
2
3
4
5
2
0
2
4
10
12
14
3
0
3
10
13
20
23
4
0
4
12
20
24
30
5
0
5
14
23
32
41

5*5 = 41.  How's that work?  In base 10, 4 * 61 + 1 * 60 = 25.
Let's see what's in the table that you already know.  0 * x = 0.  1 * x = x.  Those will be handy later.  You may also notice that the digits of the products of the highest digit, 5 14 23 32 and 41, all add up to 5.  This is true in base 10 with the digits in the products of 9 (9 18 27 36 45 54 63 72 and 81).  It turns out to be true for any base.

An example.  Multiply 34 by 24.
 

34
* 24
====
224
+1120
====
1344

Just like 3rd grade.  First we multiply 34*4.  4*4=24, write down the 4 and carry the 2.  3*4+2 = 20+2 = 22.  Then we multiply 34*2 (with a shift, since it's 20, not 2 that we're multiplying by).  4*2 = 12, write down the 2 and carry the 1.  3*2+1 = 10+1 = 11.  Then we add.  In this case there are no carried values.
 

Base 2, or Binary

In binary, we have only two distinct digits, 0 and 1.  These are commonly called bits, especially when used in computers.  All computers use binary numbers to perform arithmetic because it is so easy to build.  Electrically, if a 0 is represented by off or no voltage, then 1 is represented by on, or power.  Addition and multiplication are easy.  Recall that 0+x = x, 0 * x = 0, and 1 * x = x.  The only interesting part is what is 1+1?  In higher bases, it would be 2, but as we are in base 2, 1+1 is simply 10 (or 0, carry the 1). Here are the tables.
 
 
+
0
1
0
0
1
1
1
10
* 0 1
0 0 0
1 0 1

Not having very many choices per position leads to numbers with many bits.  Binary numbers have about 10 bits for every 3 digits in base 10.  Examples are 10 000 000 0002 is 1024, or 210 is close to 103.  This is where kilobytes, megabytes, gigabytes, terabytes, petabytes, and exabytes fit in (the 3, 6, 9, 12, 15, and 18th powers of 10 == the 10, 20, 30, 40, 50, and 60th powers of 2, approximately).

When adding binary numbers, carrying becomes important.  The bit that becomes part of the answer is 0 if the two addends are the same (0+0 = 0, 1+1 = 0, carry 1), and 1 if they are different (1+0 = 1).  Here's an example.
 
 

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

Starting on the right, 1+0 = 1.  Easy.  Then 1+1 = 0, carry a 1.  1+0+1 = 0, carry a 1.  1+1 = 0, carry a 1. 1 = 1. So the result is 10001.  In decimal, this is the same as 11+6 = 17. In some cases, there is a carry of 1, and the two bits being added are 1, so the result is a 1 with a carry of 1.

Multiplication is easy too, with only 0's and 1's.  Let's use the same numbers.
 

1 0 1 1
* 1 1 0
= = = = = = =
0 0 0 0
1 0 1 1
1 0 1 1
= = = = = = =
1 0 0 0 0 1 0

In decimal, this is 11 * 6, which is 66.  The binary value of 1000010 is 1*26 + 1*21 = 6610.  One convenience in binary multiplication is that there is never a carry value, since all products of 0 and 1 yield a single bit value.  Also notice that if the multiplier has a 0, then we can skip the step and move on.  Also notice that if the multiplier has a 1, we simply copy the multiplicand (properly shifted to the left).  Then all we have to do is add.  Inside of computers, the add is usually done in conjunction with the multiply, adding each result into an accumulator.

Inside a computer, the adding and multiplying is the easy part.  What's difficult is the carrying and the shifting of the numbers right and left.  Fortunately, designs for a single bit can be replicated and placed next to one another to form many-bit adders and multipliers.

Base 8 and Base 16, or Octal and Hexadecimal Notations

8 and 16 are powers of 2.  This allows the clustering of bits into octal or hexadecimal digits (hex needs 16 digits, so in addition to 0 - 9, the letters A B C D E and F are used for values of 10 - 15).  The clustering is much like the use of commas in large decimal numbers like the federal deficit ($2,000,000,000,000).  In octal, 3 bits are grouped together and represented by one octal digit.  In hex, groups of 4 bits are used.  In C, octal constants are written with a preceeding 0, and hex constants are written with a preceeding 0x.  You may see things like 0377 and 0x10FA.

One way to go between binary and octal is to remember that the three bits in each octal digit represent the values 4, 2, and 1.  For example, the value of 101 is 4+1 or 5.  The value of 111 is 4+2+1=7.  Hex is the same, with the left-most bit representing 8.  In time, many people can simply look at 3 or 4 bit numbers and tell you the value from memorization.  1010 is A, 0101 is 5, etc.

1028 = 10000102 = 4216

Negative Numbers

For numbers less than 0 in base 10, we typically add another symbol, the '-' or negative sign.  Negative numbers in a machine (with 0's and 1's) have one of 4 possible representations (if negative numbers are allowed).  The most obvious is to add another bit, called the sign bit, whose interpretation is pos/neg for 0/1.  Here is how 2-bit numbers with a sign bit work out with a sign bit on the left end of the number.
 
positive
value
negative
000
0
100
001
1
101
010
2
110
011
3
111
Consider what this means: Another method of representing negative numbers is to simply flip the bits, commonly called the complement representation or ones-complement representation.  This still has a sign bit on the left, but fixes at least one problem with the sign-bit representation (the ordering).
 
positive
value
negative
000
0
111
001
1
110
010
2
101
011
3
100
The complement still has the problem that there are two ways to say 0 (+0 and -0).

The third way of representing negative numbers is called the twos-complement (the complement method described above is the ones-complement).  Instead of just flipping the bits, in twos-complement, the bits are flipped and then a 1 is added to the complement to create the complemented value.  Here's how it works out.
 

positive
value
negative
000
0
000
001
1
111
010
2
110
011
3
101
Twos-complement has only one value for 0, and it has the proper ordering for comparison, regardless of the bits being interpreted as signed or unsigned (110 > 101, which means 6 > 5, or -2 > -3).  Twos-complement is used by all computers for integer values.  In the table above, there is one value not shown, 100.  This represents -4, as it is one less than -3.  In this representation, as in the two previous representations of negative numbers, the leftmost bit represents the sign.

The last representation of negative numbers is done with a bias or offset.  In this representation, if you have n numbers, the first n/2 are negative while the remaining n/2 are positive.  Essentially, the true value = stored value - bias.  As an example, 7-bit numbers are used to represent the exponent of the power in real number representations.  7-bit numbers typically represent the 128 values 0 through 127.  If a bias of 64 is introduced, then stored value of 64 means 0.  For our table of values,
 

positive
value
negative
100
0
100
101
1
011
110
2
010
111
3
001
This scheme has many nice properties, but the stored value for 0 is not all 0's.  It also has one unused bit string, 000, which represents -4 in this case.