Binary Subtraction

Date: 07/04/2003 at 16:10:06
From: Andrew
Subject: Binary Subtraction

I have looked at the examples you provided and they have been very 
helpful, but I need help understanding the rules of subtracting 
binary numbers when the subtrahend is larger then the minuend.  For 
example, I see from the answer provided in a textbook the that

 101101   
-111101

is -010000  but I can't figure out how the leading -0 was obtained in 
the answer.

Getting the first four zeros in the answer from right to left is 
pretty straightforward. Then borrowing from the 32's position gives a 
two in the 16's position, so 2 minus 1 is 1 for the answer in the 16 
position. That leaves a 0 in the minuend for the thirty two's position 
and a 1 in the subtrahend. I can't see how subtracting 1 from zero 
yields a -0 for this position as shown in the answer.

Andrew

Date: 07/04/2003 at 23:23:09
From: Doctor Peterson
Subject: Re: Binary Subtraction

Hi, Andrew.

Let's start by thinking about the more familiar base 10. You'll find 
that the same problem exists there, but you probably don't stop to 
think about it because the solution is more familiar there.

Let's subtract 61 from 45:

    45
  - 61
  ----
   -24

I just followed the usual rules for subtraction: 5-1 is 4; 4-6 is -2. 
So is the answer -24? No, because if we add 61 to -24 we get

    61
  - 24
  ----
    37

not 45. What went wrong?

The problem is that when we got that negative sign, it meant only 
that the 2 in the tens place was negative; the 4 is still positive! 
So what we realy found was that

  (40 + 5) - (60 + 1) = (40 - 60) + (5 - 1) = -20 + 4

That is not -24, but -16, which is the right answer to the problem.

So we can't subtract a larger number from a smaller one columnwise, 
because the sign gets mixed up.

The usual way to do this is to apply the fact that

  a - b = -(b - a)

to say that

  45 - 61 = -(61 - 45) = -16

You would do the same thing in binary (and these are in fact the same 
numbers):

    101101     111101
  - 111101   - 101101     
  --------   --------
           = -(010000)

That is, you reverse the order of the numbers, subtract, and take the 
negative.

Now, there are a couple of alternative ways to do this, one of which I 
don't think I've ever seen (because it doesn't save any work), while 
the other is essentially the way a computer handles the problem.

First, we can use the fact I demonstrated above, that the negative 
sign applies only to the most significant digit. In the decimal 
version of our problem, the work would look like this:

    45
  - 61
  ----
   -2 <-- subtract tens digits
     4 <-- subtract all other digits (in this case, just the ones)
  ----
   -16 <-- subtract 4 from 20, and keep the negative sign

In binary, this would be

    101101
  - 111101
  --------
    -1     <-- subtract 11 from 10
      0000 <-- subtract the rest
  --------
    -10000 <-- subtract 0 from -10000

That's not quite as simple as it looked in the decimal example, 
because just subtracting 1-1 wasn't enough to fully deal with the 
negative sign. I had to take two digits so that what remained could 
be subtracted normally. I can see why nobody uses this!

But the computer method is to represent negative numbers in "two's 
complement" form. This allows us to directly add or subtract any pair 
of numbers, including greater from smaller and negative from positive, 
and come up with the correct result, as long as we interpret it 
correctly. In this case, if I think of the numbers as having eight 
digits, a negative number -x is represented by its twos-complement, 
which is 100000000-x. To do the subtraction, I can allow myself to 
"borrow" from an imaginary ninth digit, and get

  [1]00101101
  -  00111101
  -----------
     11110000

This represents a negative number whose value can be found by taking 
its twos-complement; it is -(100000000 - 11110000) = -10000. This 
uses the fact that

  a - b = -(100000000 - [(100000000 + a) - b])

The same can be done in decimal using tens-complements, which work 
exactly the same way. In our example,

  [1]45
  -  61
  -----
     84 which means -(100 - 84) = -16

You can read more about these ideas here:

   Subtracting and Borrowing in a Column
   http://mathforum.org/library/drmath/view/61168.html 

   Two's Complement
   http://mathforum.org/library/drmath/view/54344.html 

   Subtraction Using Nine's and Ten's Complements
   http://mathforum.org/library/drmath/view/55949.html 

If you have any further questions, feel free to write back.

- Doctor Peterson, The Math Forum
  http://mathforum.org/dr.math/