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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.