Binary Arithmetic
Written by Mike James   
Article Index
Binary Arithmetic
Choosing the right base
Decimal not dead yet

Base Arithmetic

 You can count in any base you care to select. You can even use a mixed base if you want to. Just recall the examples listed earlier of money, weights and measures and you will quickly understand what mixed base counting is all about. What might surprise you a little more is that it is even possible to include negative numbers in a mixed base and it has some practical applications - but that’s another, and slightly esoteric, story!

What is also important about a place value system, any place value system, is that it makes the algorithms of arithmetic very simple.

You may not be aware that there is anything so difficult about arithmetic that it needs anything as dignified as an “algorithm” but that’s just because you’re not a Roman. As I suggested earlier, doing arithmetic using Roman numerals is a big problem. You can just about manage addition but multiplication and division are next to impossible - try and figure out how to do IX times IIIV as a algorithm that doesn't first convert to decimal or any other place value system.

The place value algorithms allow you to work out a sum by processing each pair of digits in turn and handling “carries” to the next place. What is interesting is that the algorithms are the same no matter what base you are working in - as long as you remember to stay in the original base as you work.

For example, if you want to add 22 to 21 in base three you would add the first digits, 2+1 to get the result 10. If you added them and got 3 then you are forgetting to stay within the base that you are working in!

So the result of adding the first two digits is 0 carry 1. Adding the next two digits 2+2 gives the result 11 and adding the carry gives 12. The final answer to 22+21 is 120 - in base three.

 

sumcarry

 

The general idea is that you add the symbols up in each position and then carry any result that is too big into the next positions addition. This means you only need to know how to add the basic symbols of the number system and you can then add any pair of numbers.

Why Binary?

The same sort of addition algorithm will work in any number base so why choose binary for computers?

The answer is that, initially at least, the choice of binary wasn’t at all obvious.

When Babbage planned his giant mechanical computer the obvious choice was decimal.

Why?

Simply because he could build cogs and gears that counted in lots of ten and this was the arithmetic system he was used to.

More to the point building a decimal computer allowed the values to be entered without the complication of converting to base 2. After all this is the scheme that was used by all of the mechanical calculators that predated Babbage’s idea and that came after it.

You could build a binary mechanical computer and it would have been simpler and perhaps might even have been within the capabilities of Babbage’s day but it wasn’t an obvious thing to do. It wasn’t even an obvious thing to do in the early days of the electronic computer - but it probably should have been.

Logic and switches

After George Boole had described his Boolean logic, and after various people had built logical machines based on it, the simplicity of the “true/false” algebra was beginning to be understood.

Charles Pierce sketched out how batteries and switches could be used to calculate logic but this was ahead of its time. Fifty years later in the 1940 Claude Shannon looked at the ideas again and noticed that he could build not just logic circuits using high and low voltages to represent true and false, he could also build arithmetic circuits.

All you have to do is write down the addition table for binary arithmetic for a single “digit” or bit:

       A + B = R
       0   0   0
       0   1   1
       1   0   1
       1   1   0

You might recognise this as the truth table for the Exclusive OR and this is indeed all that is needed to add two bits together - as long as you are prepared to ignore the carry.

In other words the addition table for binary symbols is the same as the Exclusive OR in logic.

If you want to generate the carry then you need to add another column to the logic table

       A + B = R C
       0   0   0 0
       0   1   1 0
       1   0   1 0
       1   1   0 1

Now you can see that the carry is simply an And operation.

Put the two together and you can add two bits and generate a result and a carry - this is called a half adder because it doesn’t deal with the problem of taking account of anything that might have been generated by an earlier pair of bits being added.

 

halfadd
A half adder takes two bits and adds them to give a result and a carry

To create a full adder all we need to do is combine two half adders so that the first adds the two bits to produce a result and a carry and the second adds the result and the carry to produce a final result and a final carry.

 

fulladd

A full adder takes two bits and the carry from the previous addition and produces a result and a carry

<ASIN:0425176444>

<ASIN:0767917073>

<ASIN:B002B101FK@COM>

<ASIN:3540689028>

<ASIN:0780334264>



 
 

   
RSS feed of all content
I Programmer - full contents
Copyright © 2014 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.