Binary - Negative Numbers
Binary - Negative Numbers
Written by Mike James   
Article Index
Binary - Negative Numbers
Complementary Arithmetic

Binary arithmetic is easy, so easy a computer can do it, but what about negative numbers? This is altogether more tricky and isn't just a matter of putting a negative sign in front of the number.

Being negative about binary

Binary is the computer way.

While we might carry on using our outmoded base ten methods with the most minor of excuses - why let the possession of ten fingers influence your choice of number base - computers do everything with zero and one. We have already looked the basics of why binary arithmetic is so attractive from a computer's point of view.

Put simply you can represent a binary number using nothing but two electronic states - usually high and low voltage. You can also manipulate a binary number using Boolean logic and, while the connection between logic and arithmetic is far from obvious, it does all fit together unreasonably well.

Notice that there is no such cosy relationship between decimal notation and any sort of easy to implement logic.

Logic and arithmetic

Two-valued arithmetic and two-valued logic fit so well together that you almost don't notice that they are quite different things. You can be talking about Boolean logic one minute with truth tables, And, Or and Not gates, and the next you are dealing with half and full adders that appear to be all about logic but designed to do arithmetic.

The point is that Boolean logic simply realizes the "addition tables" that characterize binary arithmetic. That is, to add two bits together all you need is a lookup table of results:

               A B R C
               0 0 0 0
               0 1 1 0
               1 0 1 0
               1 1 0 1

If you want to add bit A to bit B to produce a two-bit result R and C then all you have to do is look up the entry in the table and read off the answer.

All arithmetic is done this way, using a lookup table, no matter what base you are working in.

Don't believe me?

Well how do you add 3 to 6?

You use a lookup table that was loaded into your, hopefully non-volatile, memory back when you were being instructed in such things. Without the lookup table you haven't a clue how to add two digits unless you actually "do" the addition, with marbles say, and count the final result.

In other words the basic addition of the symbols in any base have to be memorized in the form of a lookup table.

Once you have the addition table for the digits in any base then you can do addition of any multi-digit numbers by following the place value algorithm - add the first two digits, write down the result and pass the carry onto the addition of the next two digits and so on.

The only complication is that after the first two digits you have to involve the carry from the previous addition but this isn't too difficult.

The connection between binary arithmetic and Boolean logic is that its lookup table for addition can be treated as if it was a truth table and implemented using logic gates. What is interesting is that the lookup table for binary has only four lines but decimal has 100! You need to know what every digit added to every other digit gives as a result.

      C R
  0 0 0 0 
  0 1 0 1
  0 2 0 2
  0 3 0 3
  9 7 1 6
  9 8 1 7
  9 9 1 8

We don't really store a 100-line table in our head's because we are "clever" enough to notice the regularities - 0 added to any digit doesn't make any difference, adding one it just easy, x+y is the same as y+x and so on.

Still you do need to maintain 40 or so table entries to do decimal arithmetic and this is presumably why it is so hard to learn at first.

If we switched to binary a four-line table would at least be easy to remember.

Switching to octal

A short detour - feel free to skip to the next section.

If you think that the idea of switching our adopted base to binary is crazy it is worth pointing out that the closely related base 8 has been seriously proposed more than once.

King Charles XII of Sweden, an accomplished mathematician, proposed in 1717 that the whole country switched to base 8, then known as octonary or octonal.

Not just changing the weights measures, currency etc. but changing the way numbers were written down and arithmetic performed. He felt that base 8 or base 64 would be much more convenient for practical calculations than the old fashioned decimal system. He died in battle before he could implement the change but it is interesting to think what might have happened.

One hundred years later a Swedish engineer tried to resuscitate the plans but using base 16. Even the French nearly missed using the metric system because octal arithmetic seemed so much more appropriate.

It is also interesting to note that the common practice of calling the base 8 system “octal” rather than octonary or octonal is quite a recent invention - from around 1960. It stems from the use of 8-pin vacuum tube/valve bases and holders, which were, trademarked “Octal”.




Getting negative

Achieving addition so easily by the fusion of Boolean logic and binary doesn't really prepare you for the messiness of the next step - subtraction.

So how do we implement subtraction?

The first question is how do we represent a negative number?

Notice that this is a very subtle question because subtraction is an operation whereas a negative number is a quantity. That is 6-5 is an instruction to subtract (take away) 5 things from 6 things but -3 is an absence of three things.

You should also be able to see that negative numbers arise quite naturally from the operation of subtraction. What do you get if you subtract 6 apples from 5 apples? Answer minus one apples.

Subtraction is such a horrible operation (if you are interested, its biggest failure is that it isn't commutative i.e. x-y isn't the same as y-x) it is much better to ignore it in favour of negative numbers. Any subtraction that you want to do can be achieved by adding a negative - which in turn raises the earlier question of how do we do we represent negative numbers?

The twin problems of how do we do subtraction and how do we represent negative numbers, have a very neat single solution that was invented back in the days of mechanical decimal calculators.

Mechanical calculators represent numbers using positions on a rotating disk or drum. They work much like a odometer in that ten turns of the units wheel, notches up one turn of the tens wheel and so on. To add one to a number you turn the units wheel on by one. Equally obviously you can subtract one by turning the units wheel the other way.

Now consider what happens when the wheels are set up to read zero and you turn the units wheel back by one. If you are working with four-digit wheels then 0,0,0,0 becomes 9,9,9,9. There's nothing remarkable about this until you notice that subtracting one from zero gives you minus one and so in this system 9,9,9,9 must in some sense be a representation of minus one.




By the same reasoning 9,9,9,8 must be minus two, 9,9,9,7 minus three and so on. In general you can see that for a four-digit machine 10000-x is a representation of -x. Notice that you subtract x from a number with one more digit than the precision you are working at, i.e. 10000 has five digits.

This observation that 10000-x is a representation of -x is more than just a surface detail. These representations even behave like negative numbers.

For example, have a go at working out what you get if you add 9999 to 0100. The obvious answer is 10099 and this is just what you get when you add standard positive numbers together - but wait a minute; our supposed mechanical calculator only has four wheels how can it show 10099 which has five digits?

The answer is that it can’t and what it actually shows as the answer is just 0099. So in four-wheel arithmetic the sum 0100+9999 gives the answer 0099 and you can see that as long as you ignore the “roll over” 9999 really does behave like minus one.

In the same way 10000-x really does behave like -x when you add it to another number - as long as you remember to truncate to the number of digits we are working with.

Thus we have our solution!







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