Long Division in BinaryDate: 06/06/2000 at 18:26:50 From: Itti Jindani Subject: Binary Mathematics What is the algorithm for binary division? Kindly explain using some examples, 33 / 3 (i.e. 100001 / 11) and 33 / 4 (i.e. 100001 / 100). Date: 06/15/2000 at 11:04:57 From: Doctor TWE Subject: Re: Binary Mathematics Hi Itti - 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 your example: 100001/11 (33/3 in decimal). First, we write it in "long-division form": _________ 11 ) 100001 Since 11 has two bits (digits), we look at the first two bits of 100001. Can 11 go into 10...? No, so we move one digit to the right. Can 11 go into 100...? Yes, exactly once. So we put a 1 in the quotient above the 100, subtract, and carry down the next bit. We now have: ____1____ 11 ) 100001 11 ----- 10 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 Moving one place over, can 11 go into 10? No, so we record a 0 in the quotient and carry down the next bit: ____10___ 11 ) 100001 11 ----- 100 Moving over another place, can 11 go into 100? Yes, so we record a 1 in the quotient, subtract, and carry down the next bit: ____101__ 11 ) 100001 11 ----- 100 11 ---- 11 One last time, we move over another place. Can 11 go into 11? Again, the answer is yes, so we record another 1 and subtract: ____1011_ 11 ) 100001 11 ----- 100 11 ---- 11 --- 0 Since the result of the subtraction is zero, we're done and we have an exact answer: 100001/11 = 1011 (33/3 = 11 in decimal). If the number is not a whole number, we can add a "radix point." This is the equivalent of a decimal point, but of course we don't call it a "decimal" point in other bases. For your second example, 100001/100 (33/4 in decimal), we do it similarly for the whole number portion, like so: ___1000_ 100 ) 100001 100 ------ 0001 (Note that I carried down a 0 twice, then a 1 in the final place.) Now I have a choice of how I can represent the answer: In "Quotient/Remainder" form: 1000 r 1 (8 r 1 decimal) In "Fractional" form: 1000 1/100 (8 1/4 decimal) Or I can continue the division and represent the answer in radix form. I put a radix point in the divisor and the quotient, and add trailing zeroes. Then I continue and carry down the next digit: ___1000.____ 100 ) 100001.000 100 ---------- 0001 0 Can 100 go into 10? (Note that I ignore the radix point when determining whether 100 goes into 10 - just as in a decimal division with a fractional part.) No, so I carry down the next digit: ___1000.0___ 100 ) 100001.000 100 ---------- 0001 00 Can 100 go into 100? Yes, so I subtract (note that I also ignore the radix point when doing the subtraction): ___1000.01__ 100 ) 100001.000 100 ---------- 0001 00 1 00 ---- 0 Since the result of the subtraction is zero, we can stop and we have an exact answer: 100001/100 = 1000.01 (33/8 = 8.25 in decimal.) This is the third form of the answer: In "Quotient/Remainder" form: 1000 r 1 (8 r 1 decimal) In "Fractional" form: 1000 1/100 (8 1/4 decimal) In "radix" form: 1000.01 (8.25 decimal) 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 dividend (the 100 in this example) had 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 the radix points right 3 places (you'll have to add zeroes to the dividend). Then divide 11001100 by 11001. For some more examples and explanations in our archives, look at: 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: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/