Binary Numbers, Arithmetic, and Radix Conversions

Binary Numbers

Computers work through a serendipitous interplay of four developments: We are interested in the first three items.

Arithmetic in radixes other than 10

Remember that a number actually represents a polynomial: 12,573 means 1*10,000 + 2*1,000 + 5*100 + 7*10 + 3*1. Alternatively, we could write it as

1*104 + 2*103 + 5*102 + 7*101 + 3*100

It turns out that there's absolutely nothing sacred about our choice of 10 for a number radix -- the ancient Babylonians used 60, and the Hebrews used 10 for some purposes and 12 for others (our clock is a vestige of both of these pieces of historical trivia). So, instead of 10, we could use 8, 16, 79, 13... as we please.

In general, we can define any number radix r we want: the digits go from 0 to r-1, and the base is r (so it's 10 for decimal, and so forth).

Let's take a number like 54 10 (5*101 + 4*100). It's easy to verify that 54 = 3*16 + 6, or 3*161 + 6*160. Notice that this has the same form as we used above to ``decode'' a number in radix 10; this tells us that 54 10 = 36 16 . And, it turns out that there is a simple algorithm for converting numbers between any two radixes. We'll get to that in a minute.

A spectacularly useful radix for our purposes is binary: base 2. This is because

  1. we can represent numbers in it
  2. binary arithmetic operations can be implemented using boolean logic
  3. boolean logic operations can be implemented easily with digital electronics.

Let's take a look at a number like 3510. The first number less than or equal to 35 that is a power of 2 is 32 -- that's 25. So 35 = 32 + 3. We won't use 16, 8, or 4, but we will use use 2 and 1. So 35 is

1*25 + 0 * 24 + 0 * 23 + 0 * 22 + 1*21 + 1*20,
which we'll write as 1000112

A little bit later, we'll show a better algorithm for converting between radixes.

Binary and Hexadecimal

Even though binary is a good radix to use in a computer, as we will see more later, to say the least, it's not very convenient for us - writing all those 1's and 0's gets very tedious, very quickly. Fortunately, we can use another radix for our work, which is convenient for us (though not as convenient as decimal!), and also easily converted to binary.

Notice that in a binary number, a group of four bits (this is called a nybble, by the way) can represent a value from 0 to 15. Also, notice that if we divide a number into nybbles, the nybbles start at the 160, 161, 162, ... 16n positions. In other words, nybbles act just like digits in radix 16! That's great - it means we can divide a number up into nybbles, translate each nybble, and have a radix 16 number. More compact to write, easy to translate.

We can see a slight problem with this scheme if we translate 43 into hexadecimal: we get 2*161 + 11*160. But if we look at the number 21116, how can we tell whether it's supposed to be 2*161 + 11*160, or 2*162 + 1*161 + 1*160?

The solution is that we need to come up with some more digits. The convention is to use letters of the alphabet for the numbers from 10 to 15, giving us:

DecimalBinaryHexadecimal
000000
100011
200102
300113
401004
501015
601106
701117
810008
910019
101010a
111011b
121100c
131101d
141110e
151111f

One little thing - remember that hexadecimal is a shorthand we use. All numbers internal to the computer are really binary.

Converting From Decimal to Another Radix

Division Algorithm

So, with that in mind, let's start by taking a look at how to convert between radixes.

We start by looking at what happens when we divide a decimal number by 10. For an example, we'll use 12,573. If we divide it by 10 we get 1,257, with a remainder of 3. The remainder of the division is the least significant digit of the original number. If we divide 1,257 by 10, we get 125 with a remainder of 7 This gave us the next digit. If we keep dividing by the radix, each remainder in turn is another digit.

Let's take our 37 10 and see what happens when we do a bunch of divisions by 2. A convenient way to show this is with a table, where we have one column for the current number we're working with, second for the radix, r, number base, another column for the result of dividing that number by r, and a fourth column for the digits we obtain. It looks like this:

OldRadixNewDigit
37 2 18 1
18 2 9 0
9 2 4 1
4 2 2 0
2 2 1 0
1 2 0 1

Since we obtained the results starting from the least significant digit, we read it starting at the bottom of the rightmost column of the table and working up, and the result is 1001012

This algorithm for converting a number from decimal to binary is called the division algorithm, because we divide on every step. In general, we can convert from decimal to any radix we want using this algorithm, dividing by our intended radix on every step.

Algebric Algorithm

In Douglas Adams's book The Hitchiker's Guide to the Galaxy, it is revealed that the Answer to Life, the Universe, and Everything is 42. Clearly, the Question wasn't completely thought through... later, it turns out that the Question is ``how much is 6*9?''

Surprisingly, there is a number radix in which this is correct. Let's see if we can find it by using algebra:

Given that the answer in radix 10 is 5410 and is 42r, we want to find r. We can setup the following equation:

4*r + 2 = 54
4*r = 52
r = 13

This algorithm is for converting a number from decimal to a new radix r where we know the digits of the answer. It is called the algebric algorithm, because we set up an algebra equation. In general, we can convert from decimal to any radix we want using this algorithm, given that we know the final digits for the new radix.

Converting From Binary to Decimal

We convert from binary to decimal by reversing this algorithm. The theory is that we are evaluating a polynomial using Horner's Rule; in the case of 100101 2 , we are evaluating With a little rearranging, this becomes So we take 0, multiply by 2, add 1, multiply the total by 2, add 0, and so forth. We can write this up as a table. First, we set up a table like this, using the bits in the number for the contents of the ``Digit'' column and a 0 as the first entry in the ``Old'' column:

OldDigitNewRadix
0 1  2
  0  2
  0  2
  1  2
  0  2
  1   

The way we fill in the table is we do the following on each row:

  1. Add the ``Old'' column to the ``Digit'' column and put the result in the ``New'' column
  2. If you're not on the last row, multiply the contents of the ``New'' column by the ``Radix'' you're converting from (2 in this case) and put the result in the ``Old'' column of the next row.
So when we've filled the table in, it looks like this:

Old Digit New Radix
0 1 12
2 0 22
4 0 42
8 1 92
18 0 182
36 1 37 

The decimal result is in the bottow of the ``New'' column.

I actually don't make any claim that this is easier for people to do than just looking at the positions and multiplying by the right powers. But it's a whole lot easier to put in a computer program!

This is called the multiplication algorithm, as we multiply in each step.

Addition in Binary

Now, how can we add in binary? Just like decimal, only we run out of numbers sooner...
 1111
 01101010
+01011001
---------
 11000011

3-input lookup table

Inputs Outputs
C in X Y S C out
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1

Hey! Easily defined in terms of logic!