Binary Arithmetic
Binary Arithmetic
Written by Mike James   
Thursday, 08 June 2017
Article Index
Binary Arithmetic
Binary is Best

What could be simpler than binary arithmetic? It’s just two-fingered counting and, once you know how it works, it seems natural for a computer to use it. But decimal is so built into our hands that it took quite a long time before we realized that two fingers were enough.

 

We are so used to counting and doing simple arithmetic that we tend to forget that if you don’t choose the right system then it all looks very difficult.  We also tend to think that the base ten place value system which is what we normally use is so natural it must be ... well, natural! Of course it isn't and there are lots of different ways of counting.

To understand the binary system let's first look at a system with more digits than just 0 and 1 and which used a mixed base.

The duo-decimal system

You might think that using a decimal place value system is so blindingly obvious that only an idiot would use anything else - but it isn’t that long since the UK dropped the mixed base duo-decimal monetary system,

The duo-decimal system is a good example of a mixed based system. This counted first in base 12 to get shillings, 12 pence makes one shilling, and then in base 20 to get pounds, 20 shillings makes one pound.

The imperial system of weights and measures still hangs on in both the USA and the UK and it’s even more eccentric. For example, weight is counted first to base 16 (ounces to pounds), then base 14 (pounds to stones) then base 8 (stones to cwt) and then base 20 (cwt to tons)!

So much for the attractive simplicity of the base ten place value system!

However this doesn’t mean that any old system of numbers works as well as any other. It has even been suggested that the Romans would have been better engineers if it wasn’t for their incredibly complicated mixed-base no-place value system.

Exactly how you count affects how easy it is to perform arithmetic and hence counting matters.

Base and place

So what is a “place value” system and how does it work?

The idea is that you first choose your base and arrange to have just enough symbols, any symbols you like, to count up to one less than this value.

For example, if you choose 3 as the base you need symbols for 0, 1, and 2 but you could just as easily use the symbols A, B and C. The symbols don't matter but in most cases we pick the traditional digits for values up to nine even though this risks confusion with a decimal system. 

Counting in base three leads quickly to a problem common to all counting systems that use a limited number of symbols.

What do you do when you get to 2 and need to count to 3? Remember you only have the symbols 0, 1 and 2.

The answer should be familiar to any digit-counting human - you make a group of three, i.e. 1 group of three and nothing extra,  which you write down as 10.

Notice that this is not “ten” but “one zero in base 3”.

 

base310

 

Then you carry on counting: 11 (i.e. 1 lot of 3 and 1), 12 (i.e. 1 lot of 3 and 2) and then you reach another group of 3.

So now you have two groups of 3 which you write down as 20 which is not “twenty” but “two zero in base 3”.

 

base320

 

You carry on like this until you reach 22 and adding one more makes this into three groups of three which you write 100, which means that you have one group of three groups of three.

base3100

 

Think of it as a hierarchy in which you build a group of three things each of which is in turn a group of three things and so on.

We could go on labouring this idea all day - but now you either see what is going on or you are totally confused. If you are confused then go through the same steps with the base you know best, i.e. base 10, and see what happens.

The place value system

The place value system is a remarkably clever invention because using it you can give a name to any number without the need for an infinite number of symbols.

You can see that you only need n symbols to count in base n, not n-1 because you also need zero to record no groups of n things.

You need a zero to implement a place value system because you need to indicate a place even if it is empty i.e. zero.

Conventionally we use the digits 0 to 9 for bases up to 10 and the letter of the alphabet for bases greater than ten.

The use of letters is something that makes a number system look very strange and it tends to frighten people but the principles are just the same.

For example, to count in hexadecimal, i.e. base 16, you need symbols for 0 to 15, i.e. one less than the base, and these are 0 to 9, A, B,C,D,E and F.

Counting in base 16 starts out exactly like counting base 10 i.e. 0,1,2,3,4,5,6,7,8 and 9, but you don’t go to ten next because you are counting in base 16 and you only move to the next place value when you have a group of 16 to notch up. Instead you use A for ten, B for eleven and so on until you reach F for 15.

Add one more and you have a group of 16 which you write down as 10 - again not “ten” but “one zero in base 16”.

The rest is just more of the same but it still looks odd to refer to “FF” as a number - 255 to be exact - because that’s what 15 groups of 16 plus one group of 15 add up to.

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 what about counting the days in a year? In this case we don't even stick to a single base for the first place value as a month as 28, 30 or 31 days. Thinking about these examples 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, i.e. lowest order, 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. i.e. the high order, 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.

 

<ASIN:0780334264>

<ASIN:0789736136>

<ASIN:0767917073>

<ASIN:3540689028>



Last Updated ( Sunday, 11 June 2017 )
 
 

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