Long Division in Binary

Date: 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/