Long Division in Binary
Date: 05/16/2000 at 12:14:54 From: Gina Ames Subject: Base 2 division Dear Dr. Math, My problem is 1011 base 2 divided by 11 base 2. I only know how to divide in base 10. Thank you for your help, Gina Ames
Date: 05/18/2000 at 11:43:07 From: Doctor TWE Subject: Re: Base 2 division Hi Gina - thanks for writing to Dr. Math. You can use the same algorithm as long division in decimal, but the values will go in either one time or 0 times. Let's do a similar example: 1000101 / 1100 (this is 69/12 in decimal.) First, we write it in "long division form": __________ 1100 ) 1000101 Since 1100 has four bits (digits), we look at the first four bits of 1000101. Can 1100 go into 1000...? No, so we move one digit to the right. Can 1100 go into 10001...? Yes, exactly once. So we put a 1 in the quotient above the 1100, subtract, and carry down the next bit. We now have: ______1___ 1100 ) 1000101 1100 ---- 101 Note that we have to do some borrowing to do the subtraction. If you're not familiar with binary subtraction, look at the following pages from our archives: Binary Subtraction http://mathforum.org/dr.math/problems/houston.7.25.96.html Complement of a Number http://mathforum.org/dr.math/problems/steve.7.10.96.html Next, we bring down the next digit and move one place to the right. Can 1100 go into 1010? No, so we record a 0 in the quotient and carry down the next bit, like this: ______10__ 1100 ) 1000101 1100 ------ 10101 Moving over another place, can 1100 go into 10101? Yes, so we record a 1 in the quotient and subtract: ______101_ 1100 ) 1000101 1100 ------ 10101 1100 ---- 1001 At this point, if we want an integer (whole number) answer in quotient and remainder form, we'll write it as 101 r 1001. That's 5 remainder 9 in decimal. We can also write that as 101 1001/1100 (5 9/12 decimal) by putting the remainder over the divisor. That fraction can be reduced to 101 11/100 (5 3/4 decimal) by dividing the numerator and denominator by 3. If we want a "radix" answer - the binary equivalent of 5.75 - we can continue the long division process by adding a radix point (the binary equivalent of a decimal point) and some trailing zeros on the dividend. We'll put a radix point in the quotient directly above the divisor's as well: ______101.____ 1100 ) 1000101.000 1100 ------ 10101 1100 ---- 1001 Now we can continue the long division process. We carry down the next digit (the first of our trailing zeros) and check: Can 1100 go into 10010? Note that for the subtractions, we'll ignore the radix point. Again, the answer is yes, so we record a 1 (this one is to the right of the radix point in the quotient) and subtract: ______101.1___ 1100 ) 1000101.000 1100 ------ 10101 1100 ------ 1001 0 110 0 ------ 11 00 We'll carry down the next digit one more time and move over another place. Can 1100 go into 1100? Again, the answer is yes, so we record another 1 and subtract. Since the result of this subtraction is zero, we're done and we have an exact answer: ______101.11__ 1100 ) 1000101.000 1100 ------ 10101 1100 ------ 1001 0 110 0 ------ 11 00 11 00 ----- 0 Just as with decimal, some values won't divide evenly, and we'll get a repeating fractional part. We can stop at any time, but realize that we've only found an approximation, not an exact value. One final note: If the divisor (the 1100 in this example) has a radix point in it, move the radix points in BOTH the dividend and divisor to the right an equal number of places sufficient to remove it from the divisor. For example, to divide 11001.1 by 11.001, first move both radix points right 3 places (you'll have to add zeros to the dividend.) Then divide 11001100 by 11001. For some more examples and explanations, look at these answers in our archives: Binary Operations http://mathforum.org/dr.math/problems/matt4.7.97.html Multiplying and Dividing Computer Style http://mathforum.org/dr.math/problems/hodsdon9.8.98.html 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.