Signed binary and 2's complement

Humans use signed decimal notation for integers.  We indicate whether a number is negative by preceding it with a minus sign.  For instance, 837 is positive.  (We could write  +837, but a leading positive sign is usually omitted.)  To make a number negative, just precede it with a minus sign:  , for instance.

Integers could be written in signed binary notation.  Just write the absolute value of the number in base two, and affix a negative sign if necessary.  For example,  28  and   in signed binary are

This has a lot of advantages, including convenience and clarity.  However, it has some disadvantages, one of which is that subtraction becomes very messy.  It requires borrowing, which is tricky and error prone.  Just recall all the problems you had in grade school learning to borrow in subtraction!

There are other ways to represent negative integers, one of which is complement notation.  This notation has the advantage of greatly simplifying subtraction.

Let’s see how it works in base 10.  The 10’s complement of an integer is the difference between the number and a higher power of the base.  For example, various complements of  837  are

            1000 – 837                  =         163

            10,000 – 837               =      9,163

            100,000 – 837             =    99,163

            1,000,000 – 837          =  999,163

Obtaining a 10’s complement by traditional subtraction is not pleasant.  It requires borrowing in every position!  Fortunately, there is an easier way.

1. Fix the number of places, including at least one additional  place on the left.  Supply zeros in the extra places on the left.
2. Replace each digit in the original number by  9 – digit .
3. Add  1  to the result.

For example, find the six digit 10’s complement of  837.

1. 000837
2. 999162
3. 999162 + 1 = 999163

Notice this is the same result we obtained above.

Here’s why complement notation is nice.  Consider the problem of subtracting  837  from  2146, say.  Lots of borrowing is necessary.

Now try adding the complement of  837  instead of subtracting.  Use six digits for convenience in all numbers, and throw away any carry out of the left most digit.

                           =>                   

which is the correct result.  We can subtract by adding!

This scheme works for negative results.  Consider  268 – 837 .

                         =>                   

The leading  9’s  are a signal that the number is negative.  Convert it to signed notation by reversing the complementation (subtract  1  and replace each digit by  9 – digit) or by complementing the complement and affixing a negative sign.

            999431            =>                   

Sure enough,  268 – 837 =  .

So far, we have seen the following equivalences.

            Signed decimal            10’s complement (six digits)

                                                   000163

                                                   999431

There isn’t much use for 10’s complement notation, except as a curiosity.  However, suppose we use base 2 and 2’s complement.

To convert a negative signed binary integer to 2’s complement,

1. Fix the number of bits.  Write zeros in the extra places to the left.
2. Replace each bit by  1 – bit.  Notice this amounts to reversing the 0’s and 1’s.
3. Add 1, ignoring any carry out of the left most bit.

For example, find the 2’s complement binary representation of   using eight bits.

To find the representation, first convert  45  to binary.

Now pad with zeros on the left to make eight bits.

            00101101

Switch 0’s and 1’s and add  1.

              11010010

            +              1

              11010011

To sum up,

            Signed decimal      Signed binary        2’s complement binary (8 digits)

                                                     11010011

The 2’s complement of a positive number is the same as the ordinary binary, with leading zeros affixed for emphasis.

            Signed decimal      Signed binary        2’s complement binary (8 digits)

                                                     11010011

                   45                            101101            00101101

Computers subtract by adding the 2’s complement.  Suppose we ask the computer to evaluate  85 – 38.  In binary, using eight bits for convenience,

                 and     ,

so

Finally,           

In base 10, , which is the correct answer.

Computers use 2’s complement notation for negative integers instead of signed binary.  It has several advantages.

• It is easy to determine the sign of a 2’s complement number:  If it begins with  0, the number is positive; if it begins with  1, the number is negative.
• The programmer doesn’t have to teach the computer to subtract by borrowing.  Instead, it can complement and add.
• It is much simpler and less expensive to build an electronic circuit that can complement than it is to build one that can subtract by borrowing.