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/