Base 2 Subtraction and Clock Arithmetic

Date: 01/26/2001 at 23:24:53
From: Jeff Bell
Subject: How Does Base 2 Subtraction Work?

I am a volunteer math teacher for a group of 4th and 5th graders in 
our local school. We are studying base 2 numbers, and how computers 
use them.

We know that computers use the "2's complement" method to do 
subtraction of base 2 numbers. We think this is because trying to 
"borrow" in subtraction the way you might for base 10 is pretty 
confusing and difficult in base 2. We know that the "2's complement" 
method works every time. But we have no idea why it works.

Can you help us?

Thanks,
Jeff Bell

P.S. You have 27 eager young math adventurers, waiting with bated 
breath.

Date: 01/27/2001 at 01:27:23
From: Doctor Fenton
Subject: Re: How Does Base 2 Subtraction Work?

Hi Jeff,

Thanks for writing to Dr. Math. I spent some time trying to figure out
how to explain this to a class I taught several years ago, and I came 
up with the following approach, which starts with ordinary arithmetic 
first, to make the ideas clear.

A major problem in computing is subtraction. It is easy to make 
electronic circuits that can add binary numbers, but the mechanics of 
"regrouping" or "borrowing" would be very difficult to implement.

The idea that comes to the rescue is "clock arithmetic." We know that 
if it is currently 8:00, in five hours the clock will read 1:00 (not 
13:00), and if it is now 9:00, in six hours the clock will read 3:00.  
Our clock gives us a simplified base-12 number system - "simplified" 
in the sense that when we add, we neglect the regrouping or "carrying"
digit.

Since we work in base 10, let's suppose we have a clock with only 10 
numbers on it, and we will use a 0 at the top instead of 10:

                     0
                  9     1
                 8       2
                  7     3
                   6 5 4

If we want to add 5 and 7, we can think of a clock hand pointing to 5, 
and we advance the hand clockwise 7 units, until it reads 2. Our clock 
sum is what we would get if we added 5 and 7, but forgot to "carry" or 
regroup. This type of addition is sometimes called "non-carrying" 
addition. If we want to subtract 2 from 5, we can move the hand 
counterclockwise 2 units from 5, to get 3, but we could also get the 
same answer by moving clockwise 8 units from 5: that is, by adding 8 
to 5 with non-carrying addition. Similarly, if we want to subtract 4 
from 6, we could either move counterclockwise 4 units, or clockwise 6 
units. Either move would bring us to the correct answer, 2.

The number that must be added in order to perform subtraction in this 
clock arithmetic is called the "10's complement" of the number we want 
to subtract. We find it by subtracting the number from 10. So, to 
subtract 2, we compute its 10's complement 10-2 = 8 and add 8 with 
noncarrying arithmetic. To subtract 4, we find its 10's complement 
10-4=6 and add 6, and so on.

In ordinary arithmetic with signed numbers, subtracting 4 from 10 is 
the same as adding the negative of 4, -4, to 10:

      10 - 4 = 10 + (-4) .

Since in the clock arithmetic above, we get the result of subtracting 
2 by adding 8, then 8 is in a sense "-2" in clock arithmetic. From 
this point of view, we can view half of our available numbers as 
negatives: 0 is zero, neither positive nor negative; 1 through 4 are 
positive; and 6 through 9 are "negative" - 9 is "-1"; 8 is "-2"; and 
so on. 5 is its own 10's complement, so it could be considered 
either positive or negative. However, when we look at binary numbers, 
we will see that it makes more sense to consider it negative.

So far, we only looked at 1-digit numbers.  To consider two-digit 
arithmetic, we would need a clock with 100 numerals, from 0 at the top 
around to 99. For three-digit arithmetic we would need 1000 numerals, 
and so on. In two-digit arithmetic, to subtract 17, we would add 
(100-17)=83, but now, only the last carry (that is, the carry from the 
10's place into the hundred's) is ignored - we carry in the lower 
places.

So     52 - 17 is   52    and   58 - 17 is  58
                   +83                     +83
                   ----                   -----
                    35                      41  .

We still call this complement the "10's" complement, but we have to 
specify how many digits are being used.

For example, to subtract 17 in three-digit arithmetic, we need the 
3-digit 10's complement (1000-17)=983, so that

    241 - 17  is  241
                 +983
                 ----
                  224     (ignoring the last carry).

These examples should convince you that we can perform subtraction
by forming an appropriate 10's complement and adding, but computing 
the 10's complement still requires subtraction, which often still 
requires regrouping or borrowing, so it doesn't seem that we have made 
anything easier. However, in two-digit arithmetic, when we form the 
10's complement by subtracting from 100, suppose we write 100 as 99+1.
Then the 10's complement of 17 is

   100 - 17 = (99+1)-17
            = (99-17)+1 
            = 82 + 1  
            = 83 .

This subtraction will NEVER require borrowing, because the subtraction 
is always done from a number with all 9's. Similarly, to form the 
3-digit 10's complement of 17, write 1000=999+1, so that

   1000 - 17 = (999+1) - 17
             = 999 - 17 + 1
             = 982 + 1
             = 983  .

We might call this simpler number to compute the 9's complement of 17, 
so the 2-digit 9's complement of 17 is 82, and the 3-digit 9's 
complement of 17 is 982. Having found the 9's complement, we add 1 to 
get the 10's complement.  

So, to subtract 63 from 84 in 2-digit arithemetic, we find the 2-digit 
9's complement of 63
  
    99 - 63 = 36,

add 1 to get the 10's complement 37, and add 37 to 84 in 2-digit 
noncarrying arithmetic:

     84
    +37
    ---
     21   .

Now, let's switch to binary numbers, which are written with only 0's 
and 1's. To subtract 0011 from 1101 in 4-digit (or 4-bit) binary 
arithmetic, we find the 2's complement of 0011 (since we are working 
in base 2) by first finding the 1's complement of 0011 by subtracting 
011 from 1111:

    1111
   -0011
   -----
    1100 

and then adding 1 to get 1101, which we then add to 1101:

   1101
  +1101
  -----
   1010   .

Note that 1101 binary is 8+4+1=13 decimal, and 011 is 2+1=3 decimal, 
and 1010 binary is 8+2=10 decimal, so our arithmetic worked.

Note that with binary numbers, it is very easy to compute the 1's 
complement: just change every 0 to a 1 and every 1 to a zero, but 
remember that the number of binary digits MUST be specified 
beforehand, so you know how many leading zeros (which will get changed 
to 1's) to add.

Recall that with decimal digits, we said that we could consider half 
the numbers to be negative. This is still true with binary numbers.  
For example, with 3-bit binary numbers, we have 8 numbers:

        binary   decimal   2's complement   equivalent
         111        7         001             -1
         110        6         010             -2
         101        5         011             -3 
         100        4         100              ?
         011        3                          3
         010        2                          2
         001        1                          1
         000        0                          0  
     
The question mark indicates that 4 is its own 2's complement, so it 
might be considered either positive or negative. However, considering 
it as negative makes exactly half the possible numbers negative, and 
now all the negative numbers share one obvious property: their first 
bit is a 1. This bit is then often called the "sign bit," since all 
binary numbers with a 1 in the first bit correspond to negative 
numbers.

So, in summary, complements in fixed-digit arithmetic allow you to 
subtract by adding the appropriate complement with respect to the base 
of the number system, and in the binary number system, the 1's 
complement is particularly easy to compute, and the 2's complement is 
found by adding 1. This process also allows an easy representation of 
negative integers by means of complements.

I hope you find this helpful.  If I haven't addressed your question
adequately, or if you have further questions, please write again.

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

Date: 01/30/2001 at 23:46:21
From: Jeff Bell
Subject: Re: How Does Base 2 Subtraction Work?

Dear Dr. Math,

Thanks ever so much for your explanation of how and why binary complement 
subtraction works. I think it is a very good explanation. I still feel 
it will be a big challenge for me to figure out an effective way to 
communicate this to a room full of 27 4th and 5th graders.  I'll let 
you know if I come up with anything that seems to work in that respect.

Now I have another challenge for this same class: How do I explain why 
any whole number raised to the zero power is equal to 1? For that matter, 
I don't even know for sure if non-whole numbers raised to the zero power 
also equal 1.  Do they, or does that only work for whole numbers?

Thanks again for your great work and the wonderful contribution you make 
to all by doing this work.  I am so grateful for this resource.  

Jeff Bell

Date: 01/31/2001 at 11:33:04
From: Doctor Twe
Subject: Re: How Does Base 2 Subtraction Work?

Hi Jeff - thanks for writing to Dr. Math.

I saw your response to Dr. Fenton's reply as I was scanning the incoming 
questions and I thought I might add some more ideas regarding 2's 
complement - you can then sort through and choose what you think will 
best work for your particular group of kids.

I'd probably start by looking at the decimal equivalents of one's and 
two's complement, called nine's and ten's complement. The kids will 
probably be more comfortable working in base 10 initially because that's 
what they're used to. Then I'd translate them into their binary 
equivalents. Check out our archives:

  Subtraction Using Nine's and Ten's Complements
  http://mathforum.org/dr.math/problems/artus.5.27.00.html   

particularly the last part, on explaining it to a 3rd grader (without 
using algebra). You can use the borrowing-buying-selling-paying back 
analogy with binary as well, only you borrow some power of $2 (like 
$256 or $65,536) instead of some power or $10 (like $1000).

In Dr. Fenton's reply he said, "the mechanics of 'regrouping' or 
'borrowing' would be very difficult to implement [electronically]." 
That's not entirely true. I've taught a digital circuit design course 
and in it, the students had to design binary adder and subtractor 
circuits. It is actually no more difficult to design a circuit that 
subtracts with borrows than it is to design a circuit that adds with 
carries. The complexity arises when you want to make a circuit that can 
add AND subtract. If you make separate "add with carry" and "subtract 
with borrow" circuits, you then also have to design a "decision" circuit 
to determine whether to add or subtract. This decision circuit becomes 
even more complex when the inputs are allowed to be signed numbers. 
Your gate-count (a measure of circuit complexity) quickly gets very large. 
By using two's complement subtraction and two's complement signed binary 
numbers, you only need to add a few gates to the adder circuit. As an 
example, the minimum number of gates required for a 4-bit adder/subtractor 
using separate "add with carry" and "subtract with borrow" circuits is 
53 gates, while the same 4-bit adder/subtractor using 2's complements needs 
only 24 gates.

By the way, I learned the complement method of subtraction (in decimal) 
when I was in elementary school - probably around 5th grade -and I liked 
it so much (because I didn't have to learn another table), I used it 
instead of the borrow method all the way through high school. When I used 
it on a test in my high school physics class - we weren't allowed to use 
calculators - my teacher marked all of my problems wrong, saying that I 
must have copied the right answers and I was just making up numbers to make 
it look like I did some work. In order to get credit for the work on the test, 
I had to _prove_ to him that the method always worked and wasn't just 
something I made up. (In retrospect, I'm not sure if perhaps he knew of the 
method, but just wanted to make me convince myself that it always worked - 
he would be devious like that sometimes.)

As to your question on whether non-integer numbers to the zero power are 
equal to 1, the answer is yes. (Note, however, that 0^0 is undefined.) 
Check out the Dr. Math FAQ on n^0 at:

  http://mathforum.org/dr.math/faq/faq.number.to.0power.html   

This is a good starting point, and has some links to additional archive 
entries on the subject. Note that most of the algebraic arguments work 
with any real n except 0.

I hope this helps. If you have any more questions, write back.

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