Complementary arithmetic

Instead of building a half and full subtractor circuit, something that could be done using the same methods developed for addition, all we have to do is use the trick of  "add 10000-x" when we want to subtract x. Of course so far we have worked in decimal and assumed only four-digit arithmetic but it can all be generalised.

In decimal the method is know as “ten's complement” arithmetic because to obtain the representation of -x you subtract it from 10^digits, i.e. ten raised to the power of the number of digits you are working with.

In binary the same representation is called “two's complement” and the only difference is that you subtract x from 2^bits, where bits is the number of bits you are working with. It is important to remember that any extra bits you may obtain when you add numbers together have to be thrown away, i.e. you can’t  extend your working range during arithmetic.

What this means is that before you start doing arithmetic with negative number you have to fix the number of digits or bits that you regard as valid - and remember to throw any excess away. If you don't do this you will get the wrong answers.

This may seem a bit crazy when you are doing pencil and paper arithmetic but it fits in perfectly with the way computers do arithmetic. That is, you might be able to write down another digit or bit but a 16-bit computer does 16-bit arithmetic no matter what!

Two's complement sounds good but there are some complications. The first is that you have the very real problem that any number, apart from zero, can represent either a positive or a negative number. Just as 9999 could be regarded as +9999 or -1 so could 0001 be regarded as +1 or -9999. How do you keep track of the pluses and the minuses?

The best method is to divide up the number range into a section that you will regard as positive and a section that you will regard as negative.

You can do this in any way that suits your purpose but mostly the division is done so that there are roughly as many positive as negative values. For example, with a four-digit decimal ten's complement system you might use 0001 to 5000 for positive values and 9999 (-1) to 5001 (-499) for negative values. This works well but notice that there is an anomaly contained in it.

What is the negative of 5000?

The answer is that in this system there isn’t one and 0-5000 in four-digit ten's complement should be considered to generate an “overflow” error.

The second problem is how do you convert a value into its negative?

You have to subtract it from 10^digits or in binary 2^bits and this implies that you can do such a subtraction.

If you think that this is a little circular you would be right. The solution is another surprising simplicity of working in binary.

As well as the ten's complement you can also define the nine's complement which involves subtracting x from 9999. You can use the nine's complement as a representation of negative values. It has some undesirable complications but is easy to compute in that each time you simply subtract each digit of x from 9 to get -x in nine's complement. Also as 9999 is just 10000-1 you can covert from a nine's complement to a ten's complement by adding one.

Tens complement

Binary complements

Now convert all of this to binary and implement it in electronics and be amazed at how natural it all seems.

If you know how to program the first thing it all explains are those “funny” numerical ranges that you are given for variables of different sizes.

For example, a 16-bit variable or 16-bit hardware storage location is usually quoted as being capable of holding a number in the range

+32767 to -32768.

This corresponds to the positive range using 1 to 32767 and the negative range using 65535 (i.e. -1) to 32768 (i.e. -32768).

You can now see why it can’t hold quite as large a positive number as a naegative number.

The next pleasing surprise is that you can immediately tell when a number is negative by looking at the highest order bit.

For example for 16-bit values the positive range written in binary is:

         0000 0000 0000 0001

to

         0111 1111 1111 1111

and the negative range is

         1111 1111 1111 1111

to

         1000 0000 0000 0000

and so all positive numbers have a zero high order bit and all negative numbers have a one.

This means that you can interpret the high order bit as a sign bit - although we didn't design things this way. The sign bit is just a consequence of the way we have divided up the range into negative and positive numbers.

The final piece of good news is that converting a value into two's complement is very easy. First convert it into one's complement, i.e. subtract every bit of the value from 1.

As

         1-0=1

and

         1-1=0

this is equivalent to “NOTing” in the sense of Boolean logic each bit of the value.

In other words to form the one's complement all you have to do is take the logical NOT of the value.

This is easy but it gets better because all you have to do is add one and the result is two's complement. In fact you don’t even have to do the “add one” as a separate operation because you could just start any addition off with an initial carry set to 1 instead of 0. Exactly how it is done varies according to the hardware design but you can see that it isn’t difficult. In fact you should be able to see that you don't need any special hardware to do subtraction at all - simply a full adder and twos compliment arithmetic.

Why bother?

Do you really need to know about complement-based arithmetic?

The answer is, at the moment, you do if you want to be a programmer or a hardware designer.

The reason is that we are still close enough to the computer hardware we program for these things to show through. This is especially the case when you get involved in bit manipulation or change the precision of a value. Occasionally you can create serious bugs simply because you don’t realise that the positive value that your machine is displaying with lots of digits should be a negative value with far fewer digits.

Another example is the simple shift operation which is supported in many computer languages. A shift of all the bits in a number to the left multiplies the value by two. A shift to the right divides it by two. However if you are working with negative numbers as well as positive things can be more difficult. For example, if you shift a value to the left then any change in the highest most bit is equivalent to a sign change. So if you detect a change in the highest bit you have multiplied by two to the point you have caused an overflow.

Shifting to the right brings with it a similar problem. If you shift in a zero to the top-most bit you make the number positive, but if you shift in a one you make it negative. What you really need to do for a signed number is to shift in a value that is the same as the top-most bit. In most machines there are two forms of shift - logical shift introduces a zero to the top-most bit and an arithmetic shift simply keeps the top-most bit the same.

Related Articles

Binary Arithmetic

Floating point numbers

Boolean Logic

Charles Babbage

Claude Shannon

Eckert & Mauchly and ENIAC

The Greeks, George Boole and Prolog

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

<ASIN:0521878586>

<ASIN:0071431195>

<ASIN:0750645822>

<ASIN:0735611319>

<ASIN:0070650500>

<ASIN:0071452818>

<ASIN:0521370957>

<ASIN:0763741493>

<ASIN:0596510047>

<ASIN:0060512806>